Search in Rotated Sorted Array: two sorted halves, one extra condition

In the previous article on problem 153, the key observation was that in a rotated sorted array, one of the two halves around mid is always sorted. That insight let us find the rotation point — and therefore the minimum — without linear scan. Problem 33 extends exactly that idea to target search. The invariant is identical. You just need one more condition.

The problem

You're given a sorted array that has been rotated at an unknown index. All values are distinct. Find target and return its index, or -1 if it's not there. You must do it in O(log n).

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

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

nums = [1], target = 0 -> -1.

The constraints are worth reading carefully: 1 <= nums.length <= 5000, all values unique, values in [-10^4, 10^4]. Three things fall out of those immediately. The uniqueness constraint is load-bearing — the algorithm below relies on it, and problem 81 shows what breaks when you remove it. The O(log n) requirement rules out anything linear: with n up to 5000 that's a difference of roughly 13 iterations versus 5000. The bounded value range means no overflow risk, so the usual (left + right) / 2 is fine in Python; C# prefers left + (right - left) / 2 as a habit.

The "possibly rotated" phrasing matters too — an unrotated array is a valid input, and the algorithm must handle it without a special case.

Brute force: O(n)

The problem says O(log n). But it helps to write down the naive answer first, just to be clear about what you're discarding.

Linear scan. Check every element. Return when you find a match.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++)
            if (nums[i] == target) return i;
        return -1;
    }
}

Time: O(n). Space: O(1). Passes all test cases. Doesn't satisfy the problem constraint. The array has up to 5000 elements — at that scale O(n) is fast enough in practice, but the point is learning the pattern, not gaming the judge.

The interesting question is why binary search can still work on a rotated array, when the whole premise of binary search is that the array is sorted.

The invariant: one half is always sorted

A rotated sorted array looks like this: [4,5,6,7,0,1,2]. Two monotonically increasing runs joined at one seam. Not globally sorted, but structured. That structure is enough for binary search — if you can exploit it.

Pick any mid. There's only one seam in the array. Which means only one of the two halves around mid can contain it. The other half must be clean — no seam, just ascending values. Exactly one of [left, mid] or [mid, right] is sorted.

How do you tell which? Compare nums[left] and nums[mid].

• If nums[left] <= nums[mid]: the left half is sorted. The values go up continuously from left to mid. The seam, if any, is somewhere in the right half.
• If nums[left] > nums[mid]: the left half contains the seam. Values drop somewhere between left and mid. The right half [mid, right] is the sorted one.

This is the same check from problem 153. The difference is what you do once you know.

The extra condition

In 153, knowing which half is sorted was enough — the minimum is at the start of the unsorted half, so you just steer toward it. In 33, you need to locate a specific value. Knowing which half is sorted tells you where you can make a reliable range check.

If the left half is sorted (nums[left] <= nums[mid]):

• Target is in the left half if nums[left] <= target < nums[mid]. Go left.
• Otherwise it must be elsewhere. Go right.

If the right half is sorted:

• Target is in the right half if nums[mid] < target <= nums[right]. Go right.
• Otherwise it must be elsewhere. Go left.

The structure is symmetrical. Both branches follow the same logic: identify the sorted half, check if the target fits inside it, commit to one side or the other. When you can't confirm the target is in the sorted half, you rule out that half entirely and flip to the other side.

The decision tree at each step looks like this:

Modified binary search: O(log n)

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
 
        while left <= right:
            mid = (left + right) // 2
 
            if nums[mid] == target:
                return mid
 
            # Left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
 
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            if (nums[mid] == target) return mid;
 
            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
 
        return -1;
    }
}

Note the C# version uses left + (right - left) / 2 instead of (left + right) / 2. Both give the same result when left and right are non-negative, but the latter can overflow if they're large integers. A good habit to carry even when constraints make it unnecessary.

Walking through example 1: target found

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

Three iterations. The key in step 2: the range check nums[left] <= target < nums[mid] resolves correctly at the boundary. 0 <= 0 is true. 0 < 1 is true. If you use < instead of <= on the left side, you miss targets that sit exactly at nums[left].

Walking through example 2: target absent

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

Step 1: left=0, right=6, mid=3. nums[mid]=7, nums[left]=4. Left half sorted. Is 3 in [4,7)? No. Search right: left=4.

Step 2: left=4, right=6, mid=5. nums[mid]=1, nums[left]=0. Left half [0,1] is sorted. Is 3 in [0,1)? No. Search right: left=6.

Step 3: left=6, right=6, mid=6. nums[mid]=2, nums[left]=2. Left half sorted (trivially, single element). Is 3 in [2,2)? No — 3 >= 2 but 3 < 2 is false. Search right: left=7.

Loop condition left <= right fails. Return -1.

Edge cases

Single-element array. nums = [5], target = 5: left=0, right=0, mid=0, nums[mid] == target, return 0. nums = [5], target = 3: equality check fails, then nums[left] <= nums[mid] (5 <= 5), range check 5 <= 3 < 5 fails, left=1, loop exits, return -1. Both work cleanly — no special-casing needed.

Unrotated array. nums = [1,2,3,4,5], target = 3: since no seam exists, nums[left] <= nums[mid] is always true throughout the search, and the range checks reduce to ordinary binary search. The rotation case degenerates gracefully.

Target at nums[left]. The range check is nums[left] <= target, not strict <. Without <=, a target sitting exactly at the left boundary of a sorted half would be routed to the wrong side. This is the most common off-by-one error in implementations.

Target at nums[right]. Symmetrically, the right-half check is target <= nums[right]. Same reasoning — a target sitting at the right boundary must be included.

Target is the rotation point. In [4,5,6,7,0,1,2], target = 0 sits at the rotation point (index 4). Step 2 of the trace above shows this works: 0 falls inside the left sorted half [0,1) when left=4, mid=5.

Target not in array, all elements larger. nums = [5,6,7,1,2,3], target = 0: every range check fails, left and right converge and then cross, return -1. The boundary conditions ensure we never access out-of-bounds.

Complexity

Each iteration discards one half of the remaining window. The rotation doesn't change that — you always move either left up or right down. Same halving rate as standard binary search, same O(log n) analysis. Space is O(1): three pointers, no extra structures.

I'd ship the modified binary search without hesitation. The brute force is there to demonstrate what "not using the sorted structure" looks like — it's not a serious candidate for production.

What changes in problem 81 (with duplicates)

This solution assumes distinct values. That assumption is load-bearing. When duplicates exist, nums[left] == nums[mid] becomes ambiguous: it could mean the left half is sorted, or it could mean both endpoints happen to have the same value and the seam is somewhere between them.

Problem 81 (Search in Rotated Sorted Array II) adds one extra branch: when nums[left] == nums[mid] == nums[right], you can't tell which half is sorted, so you increment left and decrement right and try again. This degrades the worst case to O(n) (imagine an array of all identical values except one), but the average case stays logarithmic. The overall structure is unchanged.

Pattern recognition

Reach for this pattern when you see: sorted array, O(log n) requirement, possible rotation, and distinct values. The trigger words are "rotated", "sorted", "search", "O(log n)". Any two of those together usually means modified binary search.

More broadly: if an array isn't fully sorted but has two sorted runs stitched together, you can often apply binary search by asking "which run am I in?" at every step. That's the core skill here, not the specific conditions for this problem.

Related problems

Find Minimum in Rotated Sorted Array (153) — the invariant here (one half is always sorted) is identical to the one used in 153. Problem 153 uses it to locate the minimum; problem 33 uses it to locate a target. If 33 feels opaque, go back to 153 first and make sure the invariant clicks.

Search in Rotated Sorted Array II (81) — the same algorithm with one extra branch for duplicate values at the boundaries. The worst case degrades to O(n) but the structure stays intact.

Find First and Last Position of Element in Sorted Array (34) — binary search on a fully sorted array to find a range instead of a single index. Good practice for the half-open interval logic.

Find Peak Element (162) — another case of modified binary search where the choice of direction depends on local structure rather than a global sort order.