题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
题解
借鉴思路。链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/
本题是需要使用二分查找，怎么分是关键，举个例子：
第一类
1011110111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类
22 33 44 55 66 77 11 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。
第三类
66 77 11 22 33 44 55 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| bool search(vector<int>& nums, int target) {
int right = nums.size() - 1;
int left = 0;
int mid = (left + right) / 2;
while (left <= right)
{
while (left<mid&&nums[left] == nums[mid])left++;
mid = (left + right) / 2;
if (nums[mid] == target)return true;
if (nums[mid] > nums[right])
{
if (nums[left]>target || nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
else
{
if (nums[mid] < target && nums[right] >= target)
left = mid + 1;
else
right = mid - 1;
}
}
return false;
}
|