Can the problem also be solved by first finding the pivot?

Yes. One approach is to find the index of the smallest element first, then run normal binary search in the correct half. It also works in O(log N), but the single-pass method is usually shorter and more interview-friendly. Q3 Why is at least one half always sorted? When you cut a rotated sorted array in half, the point where the array was broken and rotated can only land in one of those two pieces. Because the original array was perfectly ordered, the half that does not contain this rotation point is guaranteed to remain perfectly sorted. By comparing the middle element with the boundaries of your search, you can immediately tell which side is untouched, allowing you to use binary search efficiency even on a shifted array.

Why can't we simply compare the target with nums[mid] like normal binary search?

Normal binary search assumes the entire array is in perfect, monotonic order. In a rotated sorted array, this order is broken into two separate sorted segments at a single pivot point. If you only compare the target with nums[mid], you only know if they are equal, but you cannot tell which direction to look next.

Does the approach change for left or right rotation?

The approach does not change because left and right rotations create the exact same structural result: a single sorted sequence broken into exactly two sorted pieces. Identical Structure: Shifting elements from front-to-back (left) or back-to-front (right) both create a higher sorted segment and a lower sorted segment. One Broken Half: No matter the rotation direction, a single middle cut (mid) can only disrupt the order of one half. State Check: The algorithm only checks the current state using nums[low] <= nums[mid]. It never needs to know how the array got there. Because one half is always sorted in both rotation styles, the exact same binary search code works for both without any changes.

Search in Rotated Sorted Array I: Distinct Elements

Q: Why does this problem mention distinct elements?

Distinct values make it easy to identify which half is sorted at each step. With duplicates, that clean decision can break, which leads to the different follow-up problem usually called Search in Rotated Sorted Array 2.

Given an integer array nums, sorted in ascending order (with distinct values) and a target value k. The array is rotated at some pivot point that is unknown. Find the index at which k is present and if k is not present return -1.

Example 1

Input: arr = [4, 5, 6, 7, 0, 1, 2], target = 0

Output: 4

Explanation: The value 0 is present at index 4.

Example 2

Input: arr = [4, 5, 6, 7, 0, 1, 2], target = 3

Output: -1

Explanation: The value 3 is not present anywhere in the array.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

The simplest idea is to ignore the rotation and check every element one by one. If the current element matches the target, its index is returned immediately. This works for every array, but it does not use any of the useful order information present in the rotated array.

Algorithm

Start from index 0 and check each element in order.
If the current element is equal to the target, return that index immediately.
If the full array is checked and no match is found, return -1.

Dry Run

Search in a Rotated Sorted Array 1 Brute Dry Run

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    /*
7    Returns the index of target in the rotated array,
8    or returns -1 if target is not present.
9    */
10    int search(vector<int>& arr, int target) {
11        // Check every element from left to right.
12        for (int i = 0; i < (int)arr.size(); i++) {
13            // Return the index as soon as the target is found.
14            if (arr[i] == target) {
15                return i;
16            }
17        }
18
19        return -1;
20    }
21};
22
23// Driver code starts
24int main() {
25    vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
26    int target = 0;
27
28    Solution obj;
29    cout << obj.search(arr, target) << endl;
30
31    return 0;
32}

Complexity Analysis

Time Complexity: O(N), N is the length of array, because the whole array may need to be scanned.

Space Complexity: O(1), because only a loop variable is used.

Optimal Approach

The key observation is that even though the entire array is rotated, at least one of the two halves around mid is always sorted.

If the left half is sorted, we can check whether the target lies within the sorted range [left, mid]. If it does, we search the left half; otherwise, we search the right half.

If the left half is not sorted, then the right half must be sorted. We then check whether the target lies within the sorted range [mid, right]. If it does, we search the right half; otherwise, we search the left half.

Therefore, rotation does not completely break binary search. It only changes how we determine which half can be safely discarded.

Algorithm

Start with two pointers, low = 0 and high = n - 1, because the target may be anywhere in the array.
Find the middle index using mid = low + (high - low) / 2.
If arr[mid] is equal to the target, return mid.
Check whether the left half from low to mid is sorted by comparing arr[low] and arr[mid].
If the left half is sorted, check whether the target lies inside that sorted range.
- If it does, move high to mid - 1 for checking inside left half.
- otherwise, move low to mid + 1 for checking right half.
If the left half is not sorted, then the right half must be sorted. Check whether the target lies inside the range from mid to high.
- If it does, move low to mid + 1 for checking inside right half.
- otherwise, move high to mid - 1 for checking left half.
Continue this process while low <= high.
If the loop ends, return -1 because the target is not present.

Dry Run

Search in Rotated Sorted Array 1 Optimal Dry Run

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  /*
  Returns the index of target in the rotated array,
  or returns -1 if target is not present.
  */
  int search(vector<int>& arr, int target) {
      // Left boundary of the current search range.
      int low = 0;
13
      // Right boundary of the current search range.
      int high = (int)arr.size() - 1;
16
      // Keep searching while a valid range still exists.
      while (low <= high) {
          // Calculate the middle index safely.
          int mid = low + (high - low) / 2;
21
          // The target is found at the middle position.
          if (arr[mid] == target) {
              return mid;
          }
26
          // Check whether the left half is normally sorted.
          if (arr[low] <= arr[mid]) {
              // The target lies inside the sorted left half.
              if (arr[low] <= target && target < arr[mid]) {
                  high = mid - 1;
              } else {
                  // The target must lie in the other half.
                  low = mid + 1;
              }
          } else {
              // The left half is not sorted, so the right half must be sorted.
              if (arr[mid] < target && target <= arr[high]) {
                  low = mid + 1;
              } else {
                  // The target must lie in the other half.
                  high = mid - 1;
              }
          }
      }
46
      return -1;
  }
49};
50
51// Driver code starts
52int main() {
  vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
  int target = 0;
55
  Solution obj;
  cout << obj.search(arr, target) << endl;
58
  return 0;
60}

Complexity Analysis

Time Complexity: O(log₂ N), N is the length of array, because one half of the search range is removed in every step.

Space Complexity: O(1), because only a few variables are used.

Interview follow-up Questions

Distinct values make it easy to identify which half is sorted at each step. With duplicates, that clean decision can break, which leads to the different follow-up problem usually called Search in Rotated Sorted Array 2.

Search in Rotated Sorted Array I: Distinct Elements

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Row wise traversal

Main Diagonal Print

Search Element in Matrix