Search in Rotated Sorted Array (LC 33)

Pattern: Binary Search on Rotated Sorted Array
Difficulty: Medium
Key Concept: At each mid, one half [left, mid] or [mid, right] is sorted; use that ordering to decide whether target can lie in that half.

Problem Statement

There is an integer array nums sorted in ascending order with distinct values, then rotated at an unknown pivot.

Given nums and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

Input

• nums — rotated sorted array of distinct integers
• target — integer to find

Output

• int — index of target, or -1

Example

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

---

1. Algorithm & Pseudocode

Brute force

1. For each index i from 0 to n - 1:
2. If nums[i] == target, return i.
3. Return -1.

Optimal

1. left = 0, right = n - 1.
2. While left <= right:
3. mid = left + (right - left) / 2.
4. If nums[mid] == target, return mid.
5. If nums[left] <= nums[mid] (left half sorted):
   • If target is in [nums[left], nums[mid]), set right = mid - 1; else left = mid + 1.
6. Else (right half sorted):
   • If target is in (nums[mid], nums[right]], set left = mid + 1; else right = mid - 1.
7. Return -1.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force works
Linear search checks every position; with distinct values, the first match is the answer.

Why we need binary search
The problem requires (O(\log n)). The array is not fully sorted globally, but locally one side of mid is always a normal sorted range.

Why one side is always sorted
Pick any mid. Either the rotation “break” is left of mid, right of mid, or at mid. In all cases, at least one of the segments from left to mid or from mid to right looks like a normal increasing range (no wrap inside that segment).

How we use the sorted half
If nums[left] <= nums[mid], values from left to mid behave like sorted. Then:

• If target lies between nums[left] and nums[mid] (inclusive on left, exclusive on right because we already checked mid), search left.
• Otherwise discard the left side and search right.

If the left half is not sorted, the right half from mid to right must be sorted (for this problem’s distinct rotation model). Apply the symmetric interval test.

Why careful inequalities
We already handle equality at mid up front. The interval checks use inclusive bounds on the sorted end that still contains possible target values—mirror the standard template you practice on paper.

ASCII — two moods at mid

Case A: left..mid is sorted
[ 4, 5, 6, 7 | 0, 1, 2 ]
 L     M        R
 nums[L] <= nums[M]  → compare target to [L, M)

Case B: right..mid is sorted
[ 6, 7, 0, 1 | 2, 4, 5 ]
 L     M        R
 nums[L] > nums[M]  → compare target to (M, R]

---

3. The Dry Run

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

Step	left	right	mid	nums[mid]	Notes
1	0	6	3	7	7 != 0; left half sorted (4<=7); 0 not in [4,7) → left = 4
2	4	6	5	1	1 != 0; left half sorted? nums[4]=0 <= nums[5]=1 yes; 0 in [0,1)? yes → right = 4
3	4	4	4	0	0 == 0 → return 4

Result: 4.

---

4. Java Solution

Brute Force

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)).

Optimal

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

Time: (O(\log n)).
Space: (O(1)).

---

5. The “Java vs. Others” Edge

• Unsigned comparison is not needed in Java here; <= on int matches LeetCode’s 32-bit values.
• The template differs from classic sorted binary search because you branch on which half is sorted, not only nums[mid] vs target.
• Iterative style fits Java well; a recursive version would add stack (O(\log n)) space without benefit.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n))	(O(1))	Linear scan.
Optimal	(O(\log n))	(O(1))	Eliminates half the range each step (typical BS behavior).