81. 搜尋旋轉排序數組 II(每日一題)

lzyprime 部落格 (github)

建立時間：2021.04.07

qq及郵箱：2383518170

leetcode 筆記

題目描述

已知存在一個按非降序排列的整數數組 nums ，數組中的值不必互不相同。

在傳遞給函數之前，nums 在預先未知的某個下标 k（0 <= k < nums.length）上進行了 旋轉 ，使數組變為 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 從 0 開始 計數）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 處經旋轉後可能變為 [4,5,6,6,7,0,1,2,4,4] 。

給你 旋轉後 的數組 nums 和一個整數 target ，請你編寫一個函數來判斷給定的目标值是否存在于數組中。如果 nums 中存在這個目标值 target ，則傳回 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 <= nums.length <= 5000
-104 <= nums[i] <= 104
題目資料保證 nums 在預先未知的某個下标上進行了旋轉
-104 <= target <= 104
           

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

code

二分。先判遞增有序區間，再判是否在有序區間内。

nums[i] <= nums[mid] && nums[i] < target && target < nums[mid] || nums[i] > nums[mid] && (target < nums[mid] || target > nums[j])

化簡：

nums[i] > nums[mid] && (nums[i] < target || target < nums[mid]) || nums[i] < target && target < nums[mid]

• c++

class Solution {
public:
    bool search(vector<int> &nums, int target) {
        int i = 0, j = nums.size() - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[i] == target || nums[mid] == target || nums[j] == target) {
                return true;
            }
            if (nums[i] == nums[mid] && nums[mid] == nums[j]) {
                ++i;
                --j;
            } else if (nums[i] > nums[mid] && (nums[i] < target || target < nums[mid]) || nums[i] < target && target < nums[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return false;
    }
};