Search Rotated Array

Table of Contents

Problem Statement Hint Try it yourself Solution Solution Explanation Runtime complexity Memory complexity Solution Breakdown

Home/

Blog/

Interview Prep/

Search Rotated Array

2 mins read

Oct 15, 2025

#include <iostream>
#include <vector>
using namespace std;
int binarySearchRotated(vector<int>& arr, int key) {
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[low] <= arr[mid]) {
            if (arr[low] <= key && key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            if (arr[mid] < key && key <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}
int main() {
    vector<int> v1 = {6, 7, 1, 2, 3, 4, 5};
  
    cout << "Key(3) found at: " << binarySearchRotated(v1, 3) << endl;
    cout << "Key(6) found at: " << binarySearchRotated(v1, 6) << endl;
    
    vector<int> v2 = {4, 5, 6, 1, 2, 3};
    
    cout << "Key(3) found at: " << binarySearchRotated(v2, 3) << endl;
    cout << "Key(6) found at: " << binarySearchRotated(v2, 6) << endl;
    return 0;
}

Solution Explanation#

Runtime complexity#

The runtime complexity of this solution is logarithmic, O(logn)O(logn).

Memory complexity#

The memory complexity of this solution is constant, O(1)O(1).

Solution Breakdown#

To tackle rotation in a binary search for a rotated array, we adjust the search range based on the middle element’s comparisons as follows:

If the element at the middle index matches the target, return the index of the middle element, as the target has been found.
If the element at the middle index is greater than or equal to the element at the start index, it implies that the left subarray (from the start to the middle) is sorted:
1. Now, check if the target falls within the range of elements from the leftmost element to the middle element. If it does, adjust the search range to focus on the left subarray.
2. Otherwise, adjust the search range to focus on the right subarray.
If the element at the middle index is less than the element at the end index, it indicates that the right subarray (from the middle to the end) is sorted:
1. Check if the target falls within the range of elements from the middle element to the rightmost element. If it does, adjust the search range to focus on the right subarray.
2. Otherwise, adjust the search range to focus on the left subarray.

To implement the algorithm:

Initialize low to 0 and high to the length of the array minus one.
Enter a while loop that continues while low is less than or equal to high.
1. Inside the loop, calculate mid using the formula low + (high - low) // 2.
2. Check if the element at the middle index matches the target. If it does, return the index of the middle element.
3. If arr[low] is less than or equal to arr[mid], it implies that the left subarray (from low to mid) is sorted:
  1. If the target falls within this range, update the high to mid - 1. Otherwise, update the low to mid + 1.
4. Otherwise, it’s obvious that arr[low] is greater than arr[mid], which it indicates that the right subarray (from mid to high) is sorted:
  1. If the target falls within this range, update the low to mid + 1. Otherwise, update the high to mid - 1.
5. If the target is not found after the loop, return -1 to indicate its absence in the array.