L81 Search in Rotated Sorted Array II

Binary Search

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example:

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

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.

• Would this affect the run-time complexity? How and why?

Solution:

• two conditions:

  • left and mid are in same side

  • left and mid are in different side

• follow up:

  • duplicates, we know nums[mid] != target, so nums[left] != target

  • based on current information, we can only move left pointer to skip one cell

  • thus in the worst case, we would have a target: 2, and array-like 11111111, then the running time would be O(n)

public boolean search(int[] nums, int target) {
    if(nums == null || nums.length == 0) return false;
    int left = 0, right = nums.length - 1;

    while(left <= right){
        int mid = left + (right - left)/2;
        if(nums[mid] == target) return true;
        if(nums[mid] > nums[left]){
            if(target <= nums[mid] && target >= nums[left]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }else if(nums[mid] < nums[left]){
            if(target >= nums[mid] && target <= nums[right]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }else left++;
    }
    return false;
}