Search in a nearly sorted array in log(n) time

Given a nearly sorted array such that each of the N elements may be misplaced by no more than one position from the correct sorted order, efficiently search a given element in it. Report if the element is not present in the input array.


An element at index i in correct sorted order can be misplaced by +/- 1 position i.e. it can be present at index (i-1) or i or (i+1) in input array.

For example,

A = [2, 1, 3, 5, 4, 7, 6, 8, 9]
x = 5

Output: Element 5 found at index 3

A = [2, 1, 3, 5, 4, 7, 6, 8, 9]
x = 10

Output: Element not found in the array


A simple solution would be to run a linear search on the array and find the index of the given element. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is circularly sorted.

We can easily solve this problem in O(log(n)) time by modifying binary search algorithm. The idea is to compare the target number with elements at A[mid – 1], A[mid] and A[mid + 1] where mid is the middle index of our search space A[low..high]. If the target is found, we return the corresponding index else we reduce our search space to left sub-array A[low..mid-2] or right sub-array A[mid+2..high] depending upon if middle element is less than the target number or not.


Download   Run Code


Download   Run Code


Element 5 found at index 3

Time complexity of above solution is O(log(n)).
Auxiliary space used by the program is O(1).

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

newest oldest most voted
Notify of

Shouldn’t the comments on line 33,34 and 39,40 be swapped? Program works just fine. Just the comments for clarity.