leetcode 81 Search in Rotated Sorted Array II

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 1:

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

Example 2:

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

Follow up:

• 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?

---

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length == 0){
            return false;
        }
        int low = 0;
        int high = nums.length -1;
		// 1 第一次二分搜索，找到最小的值
       	// 1.1 在搜索时，可能遇到收尾都是相同字符的情况，111111121,121111111，对low或者high进行处理，排除这种情况
        while(nums[low] == nums[high] && high > low) {
            high--;
        }
        // 1.2 二分搜索，注意while中为等于号时，low = mid + 1， high = mid - 1
        while(low <= high){
            int mid = low + ((high - low) >> 2);
            if(nums[mid] >= nums[0]){
                low = mid+1;
            }
            else{
                high = mid-1;
            }
        }
	    // 2 当二分结束后，low指向最小的值，但是，这里要考虑最数组只有一个数的情况
        if(target == nums[0]){
            return true;
        }
        else if(target > nums[0]){
            high = low-1;
            low = 0;
        }
        else{
            high = nums.length - 1;
        }
        // 3 第二次二分搜索， 为已排序数组的二分搜索。
        while(low <= high){
            int mid = low + ((high - low)>>2);
            if(nums[mid] == target){
                return true;
            }
            else if(nums[mid] > target){
                high = mid-1;
            }
            else{
                low = mid+1;
            }
        }
        return false;
    }
}