搜索旋轉(zhuǎn)排序數(shù)組 II

題目描述：已知存在一個按非降序排列的整數(shù)數(shù)組 nums ，數(shù)組中的值不必互不相同。

在傳遞給函數(shù)之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉(zhuǎn) ，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數(shù)）。例如， [0,1,2,4,4,4,5,6,6,7] 在下標 5 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,6,7,0,1,2,4,4] 。

給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，請你編寫一個函數(shù)來判斷給定的目標值是否存在于數(shù)組中。如果 nums 中存在這個目標值 target ，則返回 true ，否則返回 false 。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/ ??

著作權(quán)歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：二分查找法

首先，如果nums只有一個數(shù)字，直接判斷這個數(shù)字是否等于target，如果相等，返回true；否則，返回false。

如果nums不止一位，首先遍歷一遍nums獲取最大值的位置maxIndx，然后分兩種情況：

• 判斷target如果不大于nums最后一位的數(shù)，則用二分查找法查找nums中(maxIndx, nums.length - 1)中是否存在跟target值相等的元素，如果有返回相應的位置，如果沒有返回-1；

• 如果target大于nums最后一位的數(shù)，則用二分查找法查找nums中(0, maxIndx)中是否存在跟target值相等的元素，如果有返回相應的位置，如果沒有返回-1。

• 判斷二分查找的結(jié)果返回值，如果返回-1，說明沒有找到target，返回false；否則返回true。

【每日寄語】 有開始，就會有曲終人散的一天，但我從不悲觀，下個開始，會在不遠處的。