advanced10 min read·Updated October 6, 2026

Binary Search in Rotated Sorted Array: Tracing [4,5,6,7,0,1,2]

Master binary search in a rotated sorted array by tracing [4,5,6,7,0,1,2] and [2,2,2,0,2]. Learn the mental model, sorted-half rule, and duplicate traps.

By Learnisim AI·Published October 6, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Standard binary search
  • Array indexing and mid-point calculation
  • Basic understanding of time complexity (O(log n))
Binary Search in Rotated Sorted Arrays (Target = 0) 1. Distinct Rotated Array: [4, 5, 6, 7, 0, 1, 2] 4 0 5 1 6 2 7 3 (mid) 0 4 (tgt) 1 5 2 6 Step-by-Step Halving Principle Logic: • lo=0, hi=6 → mid=3 (value 7). Left half [4..7] is normally sorted. • Target 0 is NOT in [4..7]. Safely discard left half; set lo = mid + 1 = 4. • Next iteration: inspect [0, 1, 2] subarray, instantly locate 0 at index 4! 2. Duplicate Hazard Case: [2, 2, 2, 0, 2] (Target = 0) 2 0 (lo) 2 1 2 2 (mid) 0 3 (tgt) 2 4 (hi) The Duplicate Ambiguity Problem: • Here, nums[lo] == nums[mid] == nums[hi] (all equal 2). • It is impossible to determine which half is sorted! • Fallback Strategy: Shrink boundaries safely when identical extremes occur. • Increment lo++ and decrement hi-- to bypass the ambiguity trap. • Restores order-awareness without sacrificing logarithmic efficiency.
Find 0 in [4,5,6,7,0,1,2]; then 0 in [2,2,2,0,2] overview diagram
Why

Why Standard Binary Search Breaks Down When Array Rotations Disrupt Sorted Order

Phase 1: The Rotation Problem

Imagine you are given a strictly sorted array that has been rotated at an unknown pivot index, such as , and you need to locate the target 0. If you apply textbook binary search directly, you calculate a midpoint index, inspect the value, and immediately hit a wall. Standard binary search relies on a single monotonic invariant: as you move left or right, values strictly increase or decrease. But in our rotated array, the sequence climbs up to 7, drops sharply to 0, and then climbs again.
When you check the midpoint, you cannot simply say "if target is smaller, go left; if larger, go right." For instance, if your midpoint lands on 6, the left half is (sorted normally) while the right half wraps around through . A naive comparison will mistakenly discard the correct half, leading you to miss the target entirely or return a wrong index of .
To make matters worse, consider what happens when elements repeat, as in our second locked scenario: finding 0 in . Here, the boundaries become ambiguous because the outer edges and the midpoint all share the value 2. You can no longer tell whether the rotation pivot lives in the left half or the right half.
Without an adaptive strategy that inspects which half remains properly ordered, standard logarithmic search is useless on rotated data. We need a way to restore order-awareness without resorting to a costly linear scan.
Why Standard Binary Search Breaks on Rotated Arrays Standard monotonic assumptions fail when rotation pivots or duplicate bounds disrupt sorted order Scenario A: Single Rotation Pivot Target: 0 in [4, 5, 6, 7, 0, 1, 2] 4 5 6 MID 7 0 TARGET 1 2 Mid=6: Left [4..6] is sorted, Right [7..2] wraps! Standard logic fails. Scenario B: Ambiguous Duplicates Target: 0 in [2, 2, 2, 0, 2] 2 LEFT 2 2 MID 0 TARGET 2 RIGHT Left == Mid == Right (2 == 2 == 2): Sorted half is totally unknown! The Correct Adaptive Binary Search Strategy Check which half is strictly ordered before deciding where to search 1. Identify Sorted Half Compare nums[left] & nums[mid]. If nums[left] <= nums[mid], left half is normally sorted. 2. Test Target Boundary Check if target lies strictly within the sorted half's bounds [nums[l] <= target < nums[mid]] 3. Shrink & Shrink Duplicates Discard invalid half safely. If duplicates tie, do left++, right-- (O(N) worst)
Why Standard Binary Search Breaks Down When Array Rotations Disrupt Sorted Order diagram
Model

The Halving Principle: Partitioning a Rotated Array into Sorted and Unsorted Halves

Phase 2: The Halving Principle

When we examine our working sequence [4, 5, 6, 7, 0, 1, 2] with and , the midpoint index is , holding value 7. If this were a standard monotonic array, splitting at 7 would tell us everything. But here, the pivot point has warped the sequence. Yet, look closely at the left subarray from index 0 to 3: . That sub-segment is entirely in correct ascending order! Meanwhile, the right subarray contains the rotation drop.

Why One Half Stays Sorted

No matter where you drop a pivot in a singly rotated array, cutting it in half guarantees that at least one of the two resulting halves is strictly monotonic. Standard binary search relies on an ordered property to discard half the search space instantly. In a rotated array, we cannot discard based on a single global order, but we can ask two local questions at every step:
1. Is the left half normally sorted?
2. Or is the right half normally sorted?
By checking whether our target 0 falls within the numeric boundaries of that certified sorted half, we can safely prune the other half—just like classic binary search. If 0 is inside the sorted half's range, we shift our boundaries there. If not, we discard that half and search the other.

The Duplicate Hazard

Now consider our second working case: [2, 2, 2, 0, 2] with target 0. When , , and , , , and . Suddenly, our model hits an ambiguity: . We cannot tell whether the rotation boundary lives on the left or the right because identical numbers disguise the slope. This structural fracture in our model requires a fallback strategy when uniqueness is lost.
The Halving Principle: Rotated Sorted Array Binary Search At any midpoint split, exactly ONE half is strictly monotonic. Target = 0. Case A: Distinct Rotated Array [4, 5, 6, 7, 0, 1, 2] | mid = 3 (val: 7) 4 lo 5 1 6 2 7 mid 0 target 1 5 2 hi Left Half: [4 .. 7] • Certified Sorted! (4 < 7) • Target 0 is NOT in [4, 7] Prune Left (lo = mid + 1) Right Half: [7 .. 2] • Contains Rotation Drop • Target 0 IS in range [7, 2] Search Here (hi = mid - 1) Case B: Duplicate Hazard [2, 2, 2, 0, 2] | lo=0, hi=4, mid=2 (val: 2) 2 lo 2 1 2 mid 0 target 2 hi The Ambiguity Fracture: nums[lo] == nums[mid] == nums[hi] • Look at boundaries: nums[0]=2, nums[2]=2, nums[4]=2. • Identical numbers completely disguise which side holds the pivot drop. • Model fails to certify monotonicity in either half. Fallback Remedy: Increment lo++ and decrement hi-- to peel identical layers!
The Halving Principle: Partitioning a Rotated Array into Sorted and Unsorted Halves diagram
Worked example

Tracing the Binary Search Algorithm on a Rotated Array Step by Step

Phase 3:

To see how the halving principle functions in practice, let us trace our first locked example: searching for target = 0 inside the distinct rotated array nums = [4, 5, 6, 7, 0, 1, 2]. Standard binary search would fail immediately because the array is not globally monotonic, but our sorted-half check keeps us on track.

Given

- Array nums = [4, 5, 6, 7, 0, 1, 2]
- Target target = 0
- Pointers: lo = 0, hi = 6

Steps

•Iteration 1:

- Compute mid = lo + (hi - lo) / 2 = 0 + (6 - 0) / 2 = 3.
- Value at midpoint: nums[3] = 7.
- Is nums[mid] == target? 7 == 0 is false.
- Which half is sorted? Check nums[lo] <= nums[mid] (). Yes, the left half [4, 5, 6, 7] is sorted.
- Is target within the left sorted range [nums[lo], nums[mid]] ()? False. Therefore, target must lie in the right half.
- Update pointers: lo = mid + 1 = 4, hi = 6.
•Iteration 2:

- New pointers: lo = 4, hi = 6.
- Compute mid = 4 + (6 - 4) / 2 = 5.
- Value at midpoint: nums[5] = 1.
- Is nums[mid] == target? 1 == 0 is false.
- Which half is sorted? Check nums[lo] <= nums[mid] (). Yes, the left half of this sub-window ([0, 1]) is sorted.
- Is target within [nums[lo], nums[mid]] ()? True! The target falls strictly inside this sorted window.
- Update pointers: hi = mid - 1 = 4.
•Iteration 3:

- New pointers: lo = 4, hi = 4.
- Compute mid = 4 + (4 - 4) / 2 = 4.
- Value at midpoint: nums[4] = 0.
- Is nums[mid] == target? 0 == 0 is true.

Result

We successfully return index 4. Now, let us examine what happens when duplicates enter the picture with our second locked example: nums = [2, 2, 2, 0, 2] searching for target = 0.
•Iteration 1 (Duplicates):

- Pointers: lo = 0, hi = 4.
- Compute mid = 2, nums[2] = 2.
- Check sorted-half condition: nums[lo] <= nums[mid] (). This is true, but notice that nums[lo] == nums[mid] == nums[hi] (). We cannot mathematically guarantee whether the rotation boundary sits on the left or the right.
- Resolution: Shrink the ambiguity window safely by incrementing lo and decrementing hi (lo = 1, hi = 3).
•Iteration 2 (Duplicates):

- Pointers: lo = 1, hi = 3.
- Compute mid = 2, nums[2] = 2.
- Continue checking until nums[mid] == 0 at index 3.

Result for Duplicates

We successfully return index 3, avoiding infinite loops or false branch decisions caused by identical boundary elements.
Tracing Rotated Binary Search: [4, 5, 6, 7, 0, 1, 2] (Target = 0) Step-by-step trace of sorted-half checks and pointer updates Iteration 1 mid=3 (val=7) → Left half [4,5,6,7] is sorted, target not in range 4 idx 0 5 idx 1 6 idx 2 7 mid (7) 0 target 1 idx 5 2 idx 6 lo=0 hi=6 Iteration 2 mid=5 (val=1) → Left [0,1] is sorted, target is within range! Excluded (Left Half) 0 lo (0) 1 mid (1) 2 hi (2) Iteration 3 & Result: • Pointers converge: lo = 4, hi = 4 → mid = 4 • Value check: nums[4] == 0 matches target exactly! ✔ Successfully returns index 4 without getting thrown off by rotation boundary. Target Index 4
Tracing the Binary Search Algorithm on a Rotated Array Step by Step diagram
Practice

Practice Tracing Binary Search on a Rotated Array

Phase 4: Practice Your Partition Logic

Now it is your turn to apply the halving principle to a slightly mutated version of our locked example. Recall how we tracked lo, mid, and hi pointers, and how we tested whether the left or right half was sorted.
Consider searching for target = 0 in the rotated array nums = [3, 1, 2, 3, 3, 3, 3]. Notice how duplicates complicate the boundary condition at nums[lo] == nums[mid] == nums[hi]. Walk through the first iteration of this array manually using the rules we established in the worked example.
python
def search_rotated_practice(nums, target):
    lo, hi = 0, len(nums) - 1
    # Trace the first iteration here:
    # mid = (lo + hi) // 2
    pass
Apply

Applying Rotated Binary Search Patterns to Closely Related Array Search Problems

Phase 5: Apply

Having mastered how to hunt for 0 in our distinct array [4,5,6,7,0,1,2] and how to survive the duplicate pitfall in [2,2,2,0,2], we can now transfer this exact decision logic to neighboring problems. The core invariant we built—identifying which half remains conventionally sorted and shrinking boundaries—is not just a one-trick pony for finding a target index. It solves any problem where a sorted array has been cyclically shifted.
Consider a direct derivative task: instead of searching for 0, what if we need to find the rotation point (the index of the minimum element, which is 4 in our distinct array)? We use the exact same pointer mechanics. When , we know the pivot must lie strictly to the right of , so we advance . When , the pivot is at or to its left, so we set .
python
# Finding the rotation pivot index in a rotated sorted array
def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo
By keeping our mental model anchored to the two halves ( versus the rest), we can adapt this template to find peaks in mountain arrays, search in 2D sorted matrices, or handle streams of rotated ranges. The transformation requires only a minor tweak to our comparison operators while retaining the efficiency.
python
def search_rotated_with_duplicates(nums, target):
    # Apply the shrink rule (lo++, hi--) when nums[lo] == nums[mid] == nums[hi]
    pass

FAQ

How do we find 0 in the rotated array [4,5,6,7,0,1,2] using binary search?
We compute mid, identify that the left half [4,5,6,7] is sorted while the right half wraps around, check if our target falls within the sorted half, and adjust pointers accordingly until we find 0 at index 4 in O(log n) time.
What happens to standard binary search when an array is rotated?
Standard binary search assumes the entire array is monotonically increasing. In a rotated array, at least one half of any split will always remain normally sorted, but the other half will contain the rotation pivot, breaking strict monotonicity.
How do duplicate elements like in [2,2,2,0,2] affect the time complexity?
Duplicates make it impossible to determine which half is sorted when nums[lo] == nums[mid] == nums[hi]. In the worst case (e.g., all identical elements), we must increment lo and decrement hi linearly, degrading time complexity to O(n).
What is the time and space complexity of searching in a rotated sorted array?
For arrays with distinct elements, the time complexity is O(log n) and space complexity is O(1) iterative. With worst-case duplicates, time complexity degrades to O(n) while space remains O(1).

Keep learning