Search, insert and delete in a sorted array
- Difficulty Level : Easy
- Last Updated : 26 Jul, 2022
In this post search, insert and delete operation in a sorted array is discussed.
In a sorted array, the search operation can be performed by using binary search.
Time Complexity of Search Operation: O(log(n)) [Using Binary Search]
Auxiliary Space: O(log(n)) due to recursive calls
In a sorted array, a search operation is performed for the possible position of the given element by using Binary search, and then an insert operation is performed followed by shifting the elements. And in an unsorted array, the insert operation is faster as compared to the sorted array because we don’t have to care about the position at which the element is placed.
Before Insertion: 12 16 20 40 50 70 After Insertion: 12 16 20 26 40 50 70
Time Complexity of Insert Operation: O(n) [In the worst case all elements may have to be moved]
Auxiliary Space: O(1)
In the delete operation, the element to be deleted is searched using binary search, and then the delete operation is performed followed by shifting the elements.
Array before deletion 10 20 30 40 50 Array after deletion 10 20 40 50
Time Complexity of Delete Operation: O(n) [In the worst case all elements may have to be moved]
Auxiliary Space: O(log n) (As implicit stack will be used )
If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to email@example.com. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above