Search in Rotated Sorted Array

medium

A sorted array has been rotated at some pivot. Search for a target value in O(log n) time

Search in Rotated Sorted Array

Key Insight

After rotation, one half around mid is always sorted. Check if target falls in the sorted half.

Step 1Initialize
Target: 0Rotated at index 4
L
R
4
0
5
1
6
2
7
3
0
4
1
5
2
6
Search space: [0..6]

Rotated array. left=0, right=6. Looking for 0.

1 / 6

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Search in Rotated Sorted Array

After rotation, one half around mid is always sorted. Check if target falls in the sorted half.

  1. Initialize

    Rotated array. left=0, right=6. Looking for 0.

  2. Mid=3, arr[3]=7

    Left half [4,5,6,7] is sorted (arr[0]=4 <= arr[3]=7). Is target in [4..7]? No (0 < 4). Search right.

  3. Narrow Right

    left=4, right=6, mid=5, arr[5]=1. Left half [0,1] is sorted (arr[4]=0 <= arr[5]=1). Is 0 in [0..1]? Yes! Search left.

  4. Found

    left=4, right=4, mid=4, arr[4]=0 = target!

  5. Result

    Target 0 found at index 4.

  6. Key Takeaway

    One half is always sorted. Check if target is in the sorted range to decide direction.