Search in Rotated Sorted Arrays

Search in Rotated Sorted Array (LeetCode 33)

An array originally sorted in ascending order is rotated at some pivot unknown to you beforehand. Search for a target value in $O(\log N)$ time.

Core Logic

During any binary search step in a rotated array, at least one half of the current range is guaranteed to be perfectly sorted. We use this sorted half to determine if the target lies within it.

public int search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;

        if (nums[low] <= nums[mid]) { // Left half [low..mid] is ordered
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1; // Target is inside the left sorted half
            } else {
                low = mid + 1; // Target must be in the right half
            }
        } else { // Right half [mid..high] is ordered
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1; // Target is inside the right sorted half
            } else {
                high = mid - 1; // Target must be in the left half
            }
        }
    }
    return -1;
}

Search in Rotated Sorted Array II (LeetCode 81 - With Duplicates)

When duplicates exist, we cannot guarantee which half is sorted if nums[low] == nums[mid]. In such cases, we simply shrink the boundary by one (low++) to bypass the ambiguity.

public boolean search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return true;
        
        if (nums[low] == nums[mid]) {
            // Cannot determine sorted half, step forward and try again
            low++;
        } else 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 false;
}

Complexity: Worst-case $O(N)$ (if all elements are identical), but average $O(\log N)$.

Find Minimum in Rotated Sorted Array (LeetCode 153/154)

No Duplicates (LC 153)

public int findMin(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            // Gap is to the right, minimum must be there
            low = mid + 1;
        } else {
            // Right is sorted, mid could be the minimum itself
            high = mid; 
        }
    }
    return nums[low];
}

With Duplicates (LC 154)

public int findMin(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else if (nums[mid] < nums[high]) {
            high = mid;
        } else {
            // Ambiguous equality, shrink high boundary slightly
            high--;
        }
    }
    return nums[low];
}

Pattern Comparison Summary