假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,0,1,2,2,5,6] 可能變?yōu)?[2,5,6,0,0,1,2] )。

編寫一個(gè)函數(shù)來判斷給定的目標(biāo)值是否存在于數(shù)組中。若存在返回 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

解題思路

二分法，用三個(gè)索引指向左、中、右三個(gè)元素，并且左索引 < 右索引時(shí)循環(huán)尋找

1. 判斷中位數(shù)是否等于目標(biāo)， 這里中位數(shù)要取右中位數(shù)，否則容易死循環(huán)
2. 如果[中間, 右]是遞增的
   1. 且目標(biāo)值在[中間, 右]之中，則左索引賦值為中間索引
   2. 否則右索引賦值為中間索引 - 1
3. 否則[左, 中間]是遞增的
   1. 且目標(biāo)值在[左, 中間]之中，則有索引賦值為中間索引 - 1
   2. 否則左索引賦值為中間索引

• 針對(duì)極端情況有很多重復(fù)數(shù)字，當(dāng)中間數(shù)和左邊數(shù)相等時(shí)，左索引++

代碼

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int mid = (i + j) / 2 + 1;
            if (nums[mid] == target) {
                return true;
            }
            // 針對(duì)極端情況, 有很多重復(fù)數(shù)字
            while (i < j && nums[i] == nums[mid]) {
                i++;
            }
            if (nums[mid] <= nums[j]) { // 則[中間, 右]是遞增的
                // 且目標(biāo)值在[中間, 右]之中
                if (nums[mid] < target && target <= nums[j]) {
                    i = mid;
                } else {
                    j = mid - 1;
                }
            } else { // 如果[左, 中間]是遞增的
                // 且目標(biāo)值在[左, 中間]之中
                if (nums[i] <= target && target < nums[mid]) {
                    j = mid - 1;
                } else {
                    i = mid;
                }
            }
        }
        return nums[i] == target;
    }
}