LeetCode 33: Search in Rotated Sorted Array - Binary Search (Med, Java, O(log(n)) )

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

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.

Examples

Example 1:

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

Example 2:

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

Example 3:

• Input: nums = [1], target = 0
• Output: -1

Key Insights

The main challenge is that a standard binary search won't work directly because the array is rotated. However, we can still use binary search by recognizing that:

1. At least one half of the array is always sorted - When we pick a middle element, either the left half or the right half will be in sorted order.
2. We can determine which half is sorted - By comparing the leftmost, middle, and rightmost elements.
3. We can decide which half to search - Based on whether the target falls within the sorted half's range.

Algorithm Walkthrough

Step 1: Identify the Sorted Half

For any middle element nums[mid]:

• If nums[left] <= nums[mid]: The left half is sorted
• Otherwise: The right half is sorted

Step 2: Check if Target is in the Sorted Half

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

• Target is in left half if: nums[left] <= target < nums[mid]
• Otherwise, search the right half

If right half is sorted:

• Target is in right half if: nums[mid] < target <= nums[right]
• Otherwise, search the left half

Solution Explanation

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;

            // Found target
            if (nums[mid] == target) {
                return mid;
            }

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (target >= nums[left] && target < nums[mid]) {
                    // Target is in the sorted left half
                    right = mid - 1;
                } else {
                    // Target must be in the right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    // Target is in the sorted right half
                    left = mid + 1;
                } else {
                    // Target must be in the left half
                    right = mid - 1;
                }
            }
        }

        return -1; // Target not found
    }
}

Detailed Code Analysis

1. Initial Setup

int left = 0;
int right = nums.length - 1;

Standard binary search initialization with left and right pointers.

2. Binary Search Loop

while (left <= right) {
    int mid = left + (right - left) / 2;

Continue until search space is exhausted. Calculate mid to avoid integer overflow.

3. Target Found

if (nums[mid] == target) {
    return mid;
}

Direct hit - return the index immediately.

4. Determine Sorted Half

if (nums[left] <= nums[mid]) {
    // Left half is sorted
}

Key insight: If nums[left] <= nums[mid], the left portion is guaranteed to be sorted.

5. Search Decision Logic

The algorithm then checks if the target falls within the range of the sorted half:

• If yes: search the sorted half
• If no: search the other half (which may be rotated)

Visual Example

Let's trace through nums = [4,5,6,7,0,1,2], target = 0:

Initial: [4,5,6,7,0,1,2]
         left=0, right=6, mid=3
         nums[mid]=7, nums[left]=4, nums[right]=2

Since nums[left] <= nums[mid] (4 <= 7), left half [4,5,6,7] is sorted
Target 0 is NOT in range [4,7], so search right half

Next: [4,5,6,7,0,1,2]
                ↑---↑
      left=4, right=6, mid=5
      nums[mid]=1, nums[left]=0, nums[right]=2

Since nums[left] <= nums[mid] (0 <= 1), left half [0,1] is sorted
Target 0 IS in range [0,1), so search left half

Next: [4,5,6,7,0,1,2]
                ↑
      left=4, right=4, mid=4
      nums[mid]=0 == target

Found! Return index 4

Time and Space Complexity

• Time Complexity: O(log n) - Each iteration eliminates half of the search space
• Space Complexity: O(1) - Only using a constant amount of extra space

Edge Cases Handled

1. Single element array: The while loop condition handles this
2. Target not in array: Returns -1 when loop terminates
3. No rotation: Algorithm still works for normally sorted arrays
4. Target at rotation point: Handled by the sorted half logic

Common Pitfalls

1. Integer overflow in mid calculation: Use left + (right - left) / 2 instead of (left + right) / 2
2. Boundary conditions: Pay attention to <= vs < in comparisons
3. Understanding which half is sorted: The key insight that makes this problem solvable

This solution elegantly handles the rotation by leveraging the fact that one half is always sorted, allowing us to maintain the O(log n) efficiency of binary search.