lzyprime 博客 (github)
創(chuàng)建時間：2021.04.07
qq及郵箱：2383518170
leetcode 筆記
題目描述
已知存在一個按非降序排列的整數(shù)數(shù)組 nums 隧膘，數(shù)組中的值不必互不相同囤采。
在傳遞給函數(shù)之前述呐，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉 ，使數(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 處經旋轉后可能變?yōu)?[4,5,6,6,7,0,1,2,4,4] 。
給你 旋轉后 的數(shù)組 nums 和一個整數(shù) target 代虾，請你編寫一個函數(shù)來判斷給定的目標值是否存在于數(shù)組中进肯。如果 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
題目數(shù)據保證 nums 在預先未知的某個下標上進行了旋轉
-104 <= target <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處环形。
code
二分策泣。先判遞增有序區(qū)間，再判是否在有序區(qū)間內抬吟。
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;
}
};
