Search in Rotated Sorted Array

Concept

LeetCode #33. This is one of the most heavily asked Binary Search problems in interviews.
Problem: There is an integer array nums sorted in ascending order. Prior to being passed to your function, nums is possibly rotated at an unknown pivot index. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with $O(\log n)$ runtime complexity.

Original: [0, 1, 2, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 0, 1, 2]

Because the array is no longer a single straight sorted line, a standard Binary Search will completely fail. If the array is [4, 5, 6, 7, 0, 1, 2] and mid is 7, is the target 5 to the left or right of 7? The numbers warp around!

The Two Halves Strategy

The secret to this problem is a mathematical guarantee: If you cut a rotated array in half, at least ONE of the two halves will ALWAYS be perfectly sorted.

1. [4, 5, 6, 7, 0, 1, 2]. Mid is 7.
2. Look at the Left half: [4, 5, 6, 7]. It is perfectly sorted!
3. Look at the Right half: [7, 0, 1, 2]. It contains the rotation pivot. It is unsorted.

The Algorithm:

1. Find mid.
2. Check which half is the perfectly sorted half. (If nums[left] <= nums[mid], the left side is perfectly sorted).
3. Check if our target mathematically falls within the absolute boundaries of that perfectly sorted half.
   • If it does: We aggressively jump into that half (right = mid - 1), safely ignoring the chaotic rotation on the other side!
   • If it doesn’t: The target MUST be hiding in the chaotic unsorted half! (left = mid + 1).

Implementation

// Time Complexity: O(log N)
// Space Complexity: O(1)

function searchRotated(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) return mid; // Found it!

        // PHASE 1: Which side is perfectly sorted?
        if (nums[left] <= nums[mid]) {
            // The LEFT half is perfectly sorted!
            
            // Does the target mathematically belong inside this sorted window?
            if (target >= nums[left] && target < nums[mid]) {
                // Yes! Jump into the left half.
                right = mid - 1;
            } else {
                // No! It must be hiding in the chaotic right half.
                left = mid + 1;
            }
        } else {
            // The RIGHT half is perfectly sorted!
            
            // Does the target mathematically belong inside this sorted window?
            if (target > nums[mid] && target <= nums[right]) {
                // Yes! Jump into the right half.
                left = mid + 1;
            } else {
                // No! It must be hiding in the chaotic left half.
                right = mid - 1;
            }
        }
    }

    return -1; // Not found
}

The Duplicates Trap

Problem: Search in Rotated Sorted Array II (LeetCode 81). What if the array contains duplicate values?
Rotated with duplicates: [1, 0, 1, 1, 1]. Target: 0.

If left is 1, mid is 1, and right is 1… which half is sorted?
nums[left] <= nums[mid] (1 <= 1) evaluates to true. The algorithm assumes the left half ([1, 0, 1]) is perfectly sorted. But it’s NOT! The pivot 0 is hiding in there. The duplicate numbers destroyed our ability to detect the sorted half.

The Fix: If you ever encounter a situation where nums[left] === nums[mid] === nums[right], the math breaks. You must manually shrink the outer boundaries by doing left++ and right-- until the duplicates are cleared out, and then let the while loop continue its Binary Search. (This degrades the worst-case time complexity to $O(N)$).

Interview Questions

Q: In the first check if (nums[left] <= nums[mid]), why do we need the = sign?
A: Imagine the array has only 2 elements: [3, 1].
Left is index 0 (3). Right is index 1 (1).
Mid calculates to index 0 (3).
If we just check nums[left] < nums[mid], it evaluates 3 < 3, which is False. The code will assume the Right half is perfectly sorted. But the Right half is [3, 1], which is backwards!
By using <=, 3 <= 3 evaluates to True. The code correctly identifies that the Left half (which is just the single element [3]) is a perfectly sorted sub-array, allowing the logic to proceed safely.