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,

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

Download   Run Code

Java

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Nishad
Guest
Nishad

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