Search in Rotated Sorted Array

NeetCode: Search in Rotated Sorted Array · LeetCode: 33. Search in Rotated Sorted Array · Difficulty: Medium

A sorted array of distinct values was rotated. Return the index of target, or -1 if it is absent, in O(log n) time.

Example

Text

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

Brute force: linear scan

Return the first index whose value equals the target, or -1 if the loop ends.

Java

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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[] {3, 4, 5, 6, 1, 2}, 1));
        System.out.println(s.search(new int[] {3, 5, 6, 0, 1, 2}, 4));
    }
}

Output

4
-1

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

Optimal: one binary search, find the sorted half

At any mid, at least one of [lo, mid] and [mid, hi] is sorted. Decide which by comparing nums[lo] with nums[mid], check whether the target lies inside that sorted half, and keep that half or discard it.

Java

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int l = nums[lo];
            int m = nums[mid];
            int h = nums[hi];
            if (m == target) {
                return mid;
            }
            if (l <= m) {
                // left half [lo, mid] is sorted
                if (l <= target && target < m) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                // right half [mid, hi] is sorted
                if (m < target && target <= h) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[] {3, 4, 5, 6, 1, 2}, 1));
        System.out.println(s.search(new int[] {3, 5, 6, 0, 1, 2}, 4));
        System.out.println(s.search(new int[] {1}, 1));
    }
}

Output

4
-1
0

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

The indices are signed int values, so hi = mid - 1 can reach -1 and the loop condition lo <= hi ends the search.