搜尋旋轉排序數組Ⅱ（二分法實作）

題目

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如，數組 [0,0,1,2,2,5,6] 可能變為 [2,5,6,0,0,1,2] )。編寫一個函數來判斷給定的目标值是否存在于數組中。若存在傳回 true，否則傳回 false。

示例1 :

輸入: nums = [2,5,6,0,0,1,2], target = 0

輸出: true

示例 2:

輸入: nums = [2,5,6,0,0,1,2], target = 3

輸出: false

注意點

參考：搜尋旋轉排序數組（二分法實作）

1、有序數組經過旋轉後會變為部分有序的數組；

2、我們使用二分法後會出現三種情況如下：

• 情況一：無法判斷左右區間哪個是有序區間，這種情況我們隻能排除一個節點的元素，無法進行區間選擇；（如101111這種情況，則當nums[left] == nums[mid] == nums[right時]）
• 情況二：左區間為有序區間，則判斷目标節點是否在有序區間中（左區間），在，則選取左區間；否則，選取右區間；
• 情況二：右區間為有序區間，則判斷目标節點是否在有序區間中（右區間），在，則選取右區間；否則，選取左區間。

實作

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

        int left = 0; //左指針
        int right = nums.length - 1; //右指針
        while (left <= right){
            int mid = left + (right - left) / 2; //中間指針
            //如果中間值為目标值，直接傳回
            if (nums[mid] == target) return true;

			//無法判斷左邊[left，mid）是否為有序區間
            if (nums[left] == nums[mid]){
            	//隻排除一個元素
                left ++;
            //左邊[left，mid）為有序區間
            }else if (nums[left] < nums[mid]){
            	//目标值在左順序區間中
                if (target >= nums[left] && target < nums[mid]){
                	//取左區間
                    right = mid - 1;
                }else {
                	//否則，取右區間
                    left = mid + 1;
                }
            //左邊[left，mid）為無序區間（則右區間為有序區間）
            }else {
            	//目标值在右順序區間中
                if(target > nums[mid] && target <= nums[right]){
                   	//取右區間
                    left = mid + 1;
                }else {
                	//否則，取左區間
                    right = mid - 1;
                }
            }
        }
        return false;
    }