33. Search in Rotated Sorted Array

Time: O(log n)

Space: O(1)

Intuition

A rotated sorted array always has at least one "sorted half" - either [lo, mid] or [mid, hi]. Once you identify which half is sorted, checking whether the target lies in that range is a simple boundary comparison. This is what standard binary search does, but applied to the sorted half rather than the whole array.

Algorithm

1Initialise lo = 0, hi = n-1.
2While lo <= hi: compute mid = lo + (hi-lo)/2. If nums[mid] == target, return mid.
3Determine which half is sorted: if nums[lo] <= nums[mid], the left half [lo, mid] is sorted.
4Left sorted: if nums[lo] <= target < nums[mid], search left (hi = mid-1). Else search right (lo = mid+1).
5Right sorted (else): if nums[mid] < target <= nums[hi], search right (lo = mid+1). Else search left (hi = mid-1).
6Return -1 if not found.

Example Walkthrough

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

1.lo=0, hi=6, mid=3 (nums[mid]=7). nums[lo]=4 <= nums[mid]=7 -> left half sorted.
2.target=0 not in [4,7] -> search right: lo=4.
3.lo=4, hi=6, mid=5 (nums[mid]=1). nums[lo]=0 <= nums[mid]=1 -> left half sorted.
4.target=0 in [0,1] -> search left: hi=4.
5.lo=4, hi=4, mid=4 (nums[mid]=0) == target. Return 4.

Output: 4

Common Pitfalls

•Use nums[lo] <= nums[mid] (not strict <) to handle the case where lo == mid.
•Duplicate values (problem 81) break this approach - requires handling nums[lo] == nums[mid] by shrinking lo.

33.cs

// Approach: Modified binary search that handles the single rotation break in sorted order.
// At each step, at least one of [lo, mid] or [mid, hi] is guaranteed to be sorted.
// If nums[lo] <= nums[mid], the left half is sorted: check if target is in [nums[lo], nums[mid]].
// If yes, search left; otherwise search right. Apply symmetric logic when the right half is sorted.
// This elegantly handles all rotation offsets, including 0 (no rotation at all).
// Avoid the pitfall of using strict equality for boundary checks to handle duplicate edge cases.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int Search(int[] nums, int target)
    {
        int n = nums.Length;
        int low = 0, high = n - 1, mid = 0;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[low] <= nums[mid])
            {
                if (nums[low] <= target && target <= nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            else
            {
                if (nums[mid] <= target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }

        return -1;
    }
}

Was this solution helpful?