Given a sorted array with n
elements which is rotated at some point. There is a number key
which needs to be searched in this array. Write a program which searches for this key
in the array. The worst case time complexity of this solution should not exceed O(logn)
.
Example Test Cases
Sample Test Case 1
Array: 5, 6, 9, 0, 1, 2, 3, 4
Key: 6
Expected Output: 1
Explanation: Since 1
is the index of 6
Solution
Searching in a sorted array is a classic binary search problem and can be done in O(logn)
time. Since this array is rotated along some point, normal binary search cannot be applied to it.
However this problem can be solved by modifying the binary search (without affecting it’s time complexity) by making the following observations.

Since the array was sorted (before rotation), we can think of this array as concatenation of two separate sorted arrays. for example array
5, 6, 9, 0, 1, 2, 3, 4
can be thought of as two concatenation of5, 6, 9
and0, 1, 2, 3, 4

Since, the 2 parts of the above array are themselves sorted, we can apply normal binary search on these parts. The only problem is that we don’t know the length of each of these two sorted parts.

The 1^{st} element of the whole array combined will always be greater than the last element. Let us call the 1^{st} element as
start
and the last element asend
. So it means thatstart > end
.
Now, when we apply binary search to the problem either of these 4 cases can happen:

Case 1 : Both the
arr[mid]
and thekey
are less than theend
. It means they are in the same half and we can apply normal binary search. 
Case 2 : Both the
arr[mid]
and thekey
are greater thanstart
. It means they are in the same half and we can apply normal binary search. 
Case 3 : The
key
is less thanend
butarr[mid]
is greater than start. It means in this case, we need to change direction (to getmid
in the same half askey
) before applying normal binary search.
So in this case we will dolo = mid + 1

Case 4 : The
key
is greater thanend
butarr[mid]
is less than start. It means in this case, we need to change direction (to getmid
in the same half askey
) before applying normal binary search.
So in this case we will dohi = mid  1
Therefore, to solve this problem we will start by applying normal binary search and then depending on which case we find, we will either apply normal binary search or we will try to switch direction and try to either go to the right half or to the left half.
See the code below for implementation
Implementation
#include <iostream> #include <vector> using namespace std; // Used to check which case we are in and give appropriate direction. // 0 means Do normal binary search int getDirection(vector<int>& arr, int mid, int key) { int start = arr[0]; int end = arr[arr.size()  1]; if (arr[mid] <= end && key <= end) { return (0); } else if (arr[mid] >= start && key >= start) { return (0); } else if (arr[mid] >= start && key < start) { return 1; } else { return 1; } } int main() { vector<int> arr = {5, 6, 9, 0, 1, 2, 3, 4 }; int key = 6; int lo = 0, hi = arr.size()  1; int mid; int ans = 1; while (lo <= hi) { mid = lo + (hi  lo)/2; if (arr[mid] == key) { ans = mid; break; } else { int direction = getDirection(arr, mid, key); // Case 3 if (direction > 0) { lo = mid + 1; } // Case 4 else if (direction < 0) { hi = mid  1; } // Case 1 and 2 (applying normal binary search) else { if (arr[mid] < key) { lo = mid + 1; } else { hi = mid  1; } } } } if (ans == 1) { cout << "Key " << key << " not found\n"; } else { cout << "Key " << key << " found at " << ans << " position\n"; } return 0; }