← DSA Atlas
Dedicated problem page · #33

Search in Rotated Sorted Array

MediumBinary SearchBinary search on a rotated arrayBinary search with sorted-half detection
Solve on LeetCode ↗
33
MediumBinary SearchBinary search with sorted-half detectionBinary search on a rotated array

Search in Rotated Sorted Array

Given an integer array nums that was originally sorted in ascending order with distinct values, then possibly rotated at an unknown pivot, and a target value, return the index of target if it is in nums, otherwise return -1. You must run in O(log n) time.

Open official problem prompt ↗
In plain English

Locate a target in a sorted-then-rotated array in logarithmic time by exploiting the structure that one half is always sorted.

Picture it like this

Imagine a clock face cut and rejoined at a random hour. Even though the '12' may not be at the top, any half you look at still runs in order, so you can tell at a glance whether your hour falls in that stretch.

Example
Input
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output
4
Why
The value 0 sits at index 4 in the rotated array.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4All values of nums are uniquenums is an ascending array possibly rotated-10^4 <= target <= 10^4
Pattern lesson

See the pattern, then code

Binary search on a rotated array
Recognition clue

A sorted array that has been rotated, plus an explicit O(log n) requirement, signals a modified binary search rather than a linear scan.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. At any midpoint, at least one of the two halves [lo..mid] or [mid..hi] is still perfectly sorted; check whether target lies inside that sorted half to decide which way to move.

New words, made simpleKnow these before the algorithm
Rotation pivot
The index where the smallest element sits after rotation; the array wraps around here.
Sorted half
The contiguous side of mid whose endpoints are in ascending order without crossing the pivot.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan

Correct but violates the required O(log n) bound.

Walk every element checking for target.

Time O(n)Space O(1)
Find pivot then binary search twice

Works but needs two passes and more bookkeeping.

First binary-search the rotation pivot, then binary-search the correct sorted segment.

Time O(log n)Space O(1)
Best choiceOne-pass modified binary search

Single clean pass, the standard interview answer.

Detect the sorted half at each step and decide direction directly.

Time O(log n)Space O(1)
The rule we keep true

Invariant

If target exists in nums, it always lies within the current [lo, hi] window.

Why this is correct

Reasoning

Because values are distinct, comparing nums[lo] with nums[mid] unambiguously identifies the sorted half. If target falls inside that half's known range we discard the other half; otherwise the target must be in the other half. Each step halves the window, guaranteeing logarithmic convergence.

The algorithm in three movesSay these aloud before coding
1Compute mid and return it if nums[mid] equals target

lo=0, hi=6, mid=3 -> nums[3]=7, left half sorted

2Determine which side of mid is sorted by comparing nums[lo] and nums[mid]

target 0 not in [4,7): lo=4

3If target lies within the sorted side's range, search that side; otherwise search the other side

lo=4, hi=6, mid=5 -> nums[5]=1, left half sorted, go left, hi=4, mid=4 -> found

4Repeat until lo passes hi, then return -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
40
51
62
73
04
15
26
1 · Readlo=0, hi=6
2 · AskIs nums[3]=7 the target 0?
3 · Update stateleft half [4..7] sorted
4 · Result0 not in [4,7), move lo=4
Key takeaway

The left half [4,5,6,7] is sorted; target 0 is not in it, so the search moves right.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Direct hit

    If mid already equals target we are done immediately.

  2. 2
    Lines 8-12Left half sorted case

    When nums[lo] <= nums[mid], the left side is ordered; keep it only if target lies in [nums[lo], nums[mid]).

  3. 3
    Lines 13-17Right half sorted case

    Otherwise the right side is ordered; keep it only if target lies in (nums[mid], nums[hi]].

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Array of length 1
  • Array not actually rotated (already sorted)
  • Target smaller than every element or larger than every element
  • Target equals the pivot minimum or the last element
!

Common beginner mistakes

  • Using strict < instead of <= when comparing nums[lo] and nums[mid], which mishandles the two-element case
  • Forgetting the boundary equality when checking target against the sorted range
  • Assuming the array is sorted and using vanilla binary search
Check your understanding

Why is it safe to conclude that one half is always sorted?

More in Binary Search

#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search#74Search a 2D MatrixBinary search on a flattened grid