Searching in a rotated sorted array

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 of 5, 6, 9 and 0, 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 as end . So it means that start > end .

Now, when we apply binary search to the problem either of these 4 cases can happen:

• Case 1 : Both the arr[mid] and the key are less than the end . It means they are in the same half and we can apply normal binary search.

  

• Case 2 : Both the arr[mid] and the key are greater than start . It means they are in the same half and we can apply normal binary search.

  

• Case 3 : The key is less than end but arr[mid] is greater than start. It means in this case, we need to change direction (to get mid in the same half as key ) before applying normal binary search.
  
  So in this case we will do lo = mid + 1

• Case 4 : The key is greater than end but arr[mid] is less than start. It means in this case, we need to change direction (to get mid in the same half as key ) before applying normal binary search.
  
  So in this case we will do hi = 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;
}