Search in a nearly sorted array in O(logn) 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,

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

Output: Element 5 found at index 3
 

Input:
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.

 
C++ implementation –
 

Download   Run Code

Output:

Element 5 found at index 3

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂



 



Leave a Reply

Notify of
avatar
wpDiscuz