Skip to content
Codeloom
DSA

Search in Rotated Sorted Array: Modified Binary Search

Solve Search in Rotated Sorted Array in O(log n) with modified binary search. Pivot detection, half-decision logic, and interview talking points.

·5 min read · By Codeloom
Intermediate 8 min read

What you'll learn

  • ✓How rotation breaks plain binary search and how to fix it
  • ✓How to decide which half is sorted at each step
  • ✓A clean iterative O(log n) implementation
  • ✓Edge cases around duplicates and small arrays
  • ✓How to walk an interviewer through the invariant

Prerequisites

  • •Basic [binary search](/blog/searching-binary-search)
  • •Comfort with [arrays](/blog/arrays-introduction)

Search in Rotated Sorted Array is the interview classic that proves you actually understand binary search rather than memorized it. The array is sorted, then rotated; you must find a target in O(log n).

The Problem

Given an integer array nums sorted in ascending order, possibly rotated at an unknown pivot, and an integer target, return the index of target or -1. All values are distinct.

Example:

  • Input: nums = [4,5,6,7,0,1,2], target = 0
  • Output: 4

Intuition

The key claim: for any midpoint in a rotated sorted array of distinct values, at least one of [low..mid] or [mid..high] is itself a sorted contiguous range. We can detect which by comparing nums[lo] with nums[mid]: if nums[lo] <= nums[mid], the left half contains no pivot. Once we know which half is sorted, we check whether target falls inside its value range; if yes, recurse there, otherwise into the other half. Each step halves the window, so the cost is O(log n).

Explanation with Example

nums = [4,5,6,7,0,1,2], target = 0.

  • lo=0, hi=6, mid=3, nums[mid]=7. Left half [4,5,6,7] is sorted because 4 <= 7. Is target in [4,7)? No. So lo = 4.
  • lo=4, hi=6, mid=5, nums[mid]=1. Left half [0,1] sorted, 0 <= 1. Is target in [0,1)? Yes. So hi = 4.
  • lo=4, hi=4, mid=4, nums[mid]=0. Match. Return 4.
step  lo  hi  mid  nums[mid]   sorted half       action
1    0   6   3       7       left [4..7] yes   target not in -> lo=4
2    4   6   5       1       left [0,1]  yes   target in     -> hi=4
3    4   4   4       0       --                match, return 4

Each iteration halves the window; one half is always sorted.
Binary search bounds shrinking on nums=[4,5,6,7,0,1,2], target=0

Code

Iterative modified binary search, O(log n) time and O(1) space.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = (int)nums.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
};

Edge Cases

  • Single-element array: return 0 if it matches, else -1.
  • Array not actually rotated: degenerates to standard binary search.
  • Target smaller than min or larger than max: returns -1 after log steps.
  • Two-element arrays like [3,1]: the half-sorted check still holds.
  • A duplicates variant exists that needs an extra shrink step when nums[lo] == nums[mid] == nums[hi].

Complexity Analysis

  • Brute force: O(n) time, O(1) space.
  • Modified binary search: O(log n) time, O(1) space.

You halve the search range every iteration, just with a smarter branch decision.

How to Explain It in an Interview

Start with the key claim: for any midpoint in a rotated sorted array of distinct values, one side is sorted. Prove it briefly: if nums[lo] <= nums[mid], the left side has no pivot in it. From there, the rule is mechanical. If the target falls in the sorted side’s value range, recurse there; otherwise the other side. Mention the duplicates variant to show breadth, but solve the distinct version cleanly first.

  • Find Minimum in Rotated Sorted Array
  • Search in Rotated Sorted Array II (duplicates)
  • Find Peak Element (binary search on shape)
  • Binary Search (baseline)

Wrap up

Rotated array search is the litmus test for binary search intuition. The trick is reducing to “which half is sorted” and asking “does the target fit there?” Master this template and you’ll handle peak-finding, rotation pivots, and many bound-finding variants in the same breath. Pair it with the Big-O intuition for halving.

Related articles