DSA sheet · Binary Search · Classic pattern

Search in Rotated Sorted Array

A sorted array has been "rotated": a block from the end was moved to the front. We must find a target in it. The teacher shows that we can still use binary search, even though the whole array is no longer sorted. The trick is one extra question at every step: "which half, left or right of mid, is sorted?" Once we know that, we use the sorted half to decide where the target can be.

Why it matters: this is the first problem where binary search works on an array that is not fully sorted. The same "which half is sorted" idea comes back in Minimum in Rotated Sorted Array, Find K Rotations, and many interview twists.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: linear search
• Part B · Optimal: binary search with "which half is sorted?"
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search looks at the middle element and, with one comparison, throws away half of the array. That's only allowed when we can say for sure "the answer cannot be in that half". In a sorted array that's easy: if the middle value is smaller than the target, everything to its left is even smaller, so the target can only be on the right.

Put another way, we need a yes/no question whose answers line up in order, like no no no yes yes yes. For a sorted array, "is arr[i] >= target?" is such a question. Here the array is rotated, so that simple question breaks. We'll find a new way to decide which half to throw away.

low, high and mid

• left (also called low): the first index that could still hold the answer. Starts at 0.
• right (also called high): the last index that could still hold the answer. Starts at n - 1.
• mid: the index in the middle of left..right. We check it and then move left or right past it.

Why mid = left + (right - left) // 2 and not (left + right) // 2

Both give the same number. The teacher explains why we prefer the first one. In Java or C++, an int can hold at most 2³¹ − 1. If right is already near that limit, left + right goes past it and wraps around to a negative number (overflow), so mid becomes garbage. right - left is never bigger than right, so the first form never overflows.

What is a rotated sorted array?

Start with a sorted array. One rotation (to the right) takes the last element and puts it at the front; everything else moves one place right.

sorted:            0 1 2 4 5 6 7
after 1 rotation:  7 0 1 2 4 5 6     (7 moved to the front, 0 moved from index 0 to 1)
after 2 rotations: 6 7 0 1 2 4 5
after 3 rotations: 5 6 7 0 1 2 4
after 4 rotations: 4 5 6 7 0 1 2     (0 is now at index 4)

The teacher counts the rotations by watching the smallest value: each rotation pushes 0 one step to the right. 0 is now at index 4, so the array was rotated 4 times.

The result is two sorted pieces glued together: 4 5 6 7 and 0 1 2. Inside each piece the numbers go up. There is exactly one drop (7 → 0) where the second piece starts. (If the array is rotated 0 times, or n times, there's no drop at all and it's simply sorted.)

Part A · Brute force: linear search

LeetCode 33

1The question in simple words

You get an array nums that was sorted in increasing order and then possibly rotated by some unknown amount. All values are different. You also get a target. Return the index of the target, or -1 if it isn't there.

• nums = [4,5,6,7,0,1,2], target 0 → 4
• nums = [4,5,6,7,0,1,2], target 3 → -1 (3 is not in the array)
• nums = [1], target 0 → -1

2What the constraints tell us

• Length: 1 to 5000 → the array is never empty, but it can have just 1 element. Our loop must handle that.
• Values and target: −10⁴ to 10⁴, all values unique → no duplicates, so "which half is sorted" can always be decided (duplicates make it much harder; that's a different problem).
• n ≤ 5000 is tiny: even a simple O(n) scan is about 5000 steps, far below the ~10⁸ that causes TLE. The teacher points out that the linear scan would also get accepted (and run fast).

3Intuition

Forget the rotation. Just walk from left to right and stop when you see the target.

4Why we still don't stop here

The teacher's point: when an interviewer gives you a sorted (or rotated sorted) array, they expect binary search. And if n were huge, like 10⁹ or 10¹⁰, an O(n) scan would be too slow. So linear search is only our starting point.

5Approach steps

1. For each index i from 0 to n − 1: if nums[i] == target, return i.
2. If the loop ends, return −1.

6Code (Python)

class Solution:
    def search(self, nums, target):
        for i in range(len(nums)):
            if nums[i] == target:      # found it
                return i
        return -1                      # checked everything, not there

7Code line by line

8Dry run

[4,5,6,7,0,1,2], target 0: check 4 ✗, 5 ✗, 6 ✗, 7 ✗, 0 ✓ → return 4. Five checks.

9Complexity & remember

• Time O(n): in the worst case we look at every element.
• Space O(1): just the loop variable.

Part B · Optimal: binary search with "which half is sorted?"

1The question (same as Part A)

Same input and output, but now we want O(log n) time.

2What the constraints tell us

• At least 1 element → right = n - 1 is always a valid index at the start.
• Unique values → comparing nums[mid] with nums[left] always tells us which half is sorted. This is what makes the method safe.
• Indices go only up to 4999, so the overflow worry from Part 0 doesn't apply here. We still write left + (right - left) // 2.

3Intuition: can we apply binary search here?

Normal binary search needs the whole array sorted. Ours isn't. But the teacher notices that if we look from mid, one side is always a normal sorted piece. We can only make a safe decision using a sorted piece, because only there can we say "the target is between this low end and this high end, or it isn't".

Picture 1: mid lands in the left piece

index:   0   1   2   3   4   5   6
value:   4   5   6  [7]  0   1   2
         L          M           R
         └──────────┘                left..mid = 4 5 6 7 → sorted ✓
                    └───────────┘    mid..right = 7 0 1 2 → NOT sorted ✗ (drop 7→0)

mid = 0 + (6 − 0) // 2 = 3, value 7. From index 0 to 3 the values go up: 4, 5, 6, 7. From 3 to 6 they don't: 7, 0, 1, 2. So 7 belongs to the left sorted piece, and we can trust the left half.

Picture 2: mid lands in the right piece

index:   0   1   2   3   4   5
value:   4   5  [0]  1   2   3
         L      M           R
         └──────┘                    left..mid = 4 5 0 → NOT sorted ✗ (drop 5→0)
                └───────────┘        mid..right = 0 1 2 3 → sorted ✓

mid = 0 + (5 − 0) // 2 = 2, value 0. The left half 4 5 0 is not sorted. But 0 1 2 3 is. So 0 belongs to the right sorted piece, and here we trust the right half.

4Building the conditions from examples

Condition 0: is nums[mid] the target?

Before anything else, if nums[mid] == target, we're done: return mid. The teacher puts this check first, so that every later branch knows the target is not at mid. That's why later we can use strict < at mid and move to mid - 1 / mid + 1.

Condition 1: how do we know the left half is sorted?

We only know three positions: left, mid, right. So we must decide using their values.

• If left..mid is sorted, the values climb from nums[left] up to nums[mid]. So nums[mid] >= nums[left]. In Picture 1: 7 ≥ 4 ✓.
• If mid were in the right piece instead, the right piece climbs from mid to right, so nums[mid] would be smaller than nums[right] (like 7, 8, 9, 10 going up). In Picture 1, 7 > 2, so 7 can't be in the right piece. That agrees.

Condition 2 (left half sorted): is the target inside it?

Knowing the left half is sorted does not mean the target is there. The teacher stresses this: we must check the range. A sorted piece from nums[left] to nums[mid] contains exactly the values between those two ends.

• Target 5 in [4,5,6,7,0,1,2]: the sorted left half covers 4 to 7. Is 4 ≤ 5 < 7? Yes → the target can only be in the left half → right = mid - 1.
• Target 0: is 4 ≤ 0 < 7? No. Even though the left half is sorted, 0 isn't in its range → it must be in the other half → left = mid + 1.

Condition 3 (right half sorted): is the target inside it?

Now use Picture 2, [4,5,0,1,2,3], mid value 0. The sorted right half covers 0 to 3.

• Target 2: is 0 < 2 ≤ 3? Yes → the target is in the right half → left = mid + 1.
• Target 4: is 0 < 4 ≤ 3? No. The right half is sorted, but 4 isn't in its range → search the left half → right = mid - 1.

It's the mirror of Rule 2: the end at mid is strict (already checked), and the end at right is included.

The loop: while left <= right

Every step moves left or right, so we repeat the whole thing in a loop. Why <= and not <? When left == right there is still one element to check, and it might be the target. With < we'd skip it. When left passes right, the range is empty and the target isn't there → return −1.

5Approach steps

1. Set left = 0, right = n - 1.
2. While left <= right: compute mid = left + (right - left) // 2.
3. If nums[mid] == target → return mid.
4. If nums[mid] >= nums[left] (left half sorted): if nums[left] <= target < nums[mid] → right = mid - 1, else left = mid + 1.
5. Else (right half sorted): if nums[mid] < target <= nums[right] → left = mid + 1, else right = mid - 1.
6. After the loop → return −1.

6Code (Python)

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:                 # Condition 0
                return mid

            if nums[mid] >= nums[left]:             # left half is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1                 # target is in the left half
                else:
                    left = mid + 1                  # target is in the right half
            else:                                   # right half is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1                  # target is in the right half
                else:
                    right = mid - 1                 # target is in the left half

        return -1

7Code line by line

8Dry run

Run 1: [4,5,6,7,0,1,2], target 0 (the teacher's example)

Note what happened in step 2: once we moved left to 4, we didn't know yet whether 0 1 2 was sorted. We simply computed a new mid and asked the same question again. This time both halves were sorted, and the left-branch handled it like normal binary search.

Run 2: same array, target 3 (not present)

Run 3: [4,5,0,1,2,3], target 4 (uses the right-sorted branch)

With target 2 instead: step 1 sees 0 < 2 ≤ 3 → left = 3. Then left 3, right 5, mid 4, value 2 → return 4.

9Complexity & remember

• Time O(log n): each step throws away about half of the range (n → n/2 → n/4 → … → 1), which takes about log₂ n steps. For n = 5000 that's about 13 steps instead of 5000.
• Space O(1): only three index variables.

The teacher's closing remark: on LeetCode the linear version also shows as fast, because n is only 5000. Binary search only becomes a must when n is huge (like 10⁹), but the interviewer expects it anyway.

Part C · Revision page

s = Solution()
print(s.search([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(s.search([4, 5, 6, 7, 0, 1, 2], 3))   # -1
print(s.search([4, 5, 0, 1, 2, 3], 4))      # 0
print(s.search([1], 0))                     # -1
print(s.search([3, 1], 1))                  # 1

Based on this video: Search in Rotated Sorted Array