Search in Rotated Sorted Array II

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

A sorted array (non-decreasing, duplicates allowed) was rotated at an unknown pivot, for example [0,1,2,4,4,4,5,6,6,7] rotated by 5 becomes [4,5,6,6,7,0,1,2,4,4]. Given the rotated array nums and a target, return true if target is in the array and false otherwise.

Example

Text

Input:  nums = [2,5,6,0,0,1,2], target = 0    Output: true
Input:  nums = [2,5,6,0,0,1,2], target = 3    Output: false
Input:  nums = [1,0,1,1,1],     target = 0    Output: true

Brute force: linear scan

Check every element. This is correct for any array, sorted or not.

Java

class Solution {
    public boolean search(int[] nums, int target) {
        for (int x : nums) {
            if (x == target) {
                return true;
            }
        }
        return false;
    }
}

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

Output

true
false
true
false

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

Java

class Solution {
    public boolean 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 true;
            }
            if (l == m && m == h) {
                // Cannot tell which half is sorted: drop both ends, which are not the target.
                lo++;
                hi--;
            } else if (l <= m) {
                // Left half is sorted.
                if (l <= target && target < m) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                // Right half is sorted.
                if (m < target && target <= h) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return false;
    }
}

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

Output

true
false
true
false

Time: O(log n) when few elements repeat, but O(n) in the worst case. An array like [1,1,1,1,1,1,1,0,1] (or all equal values with a target that is absent) reaches the "all three equal" branch on almost every step, and each such step removes only two elements. No algorithm does better in the worst case: with mostly equal values a single different element can be anywhere, so every position must be inspected. Space: O(1).