https://leetcode-cn.com/problems/search-in-rotated-sorted-array
二分法的复杂度是 O(log2n)，所以感觉题目就是让用二分查找，但是需要注意对各种 Case 进行分类，特别是是要测试 Pivot 所在的地方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func search(nums []int, target int) int {
for start,end:=0,len(nums)-1;start<=end; {
mid:=(start+end)/2
switch {
case nums[mid]==target:
return mid
case nums[start]==target:
return start
case nums[end]==target:
return end
case nums[mid]>target && nums[start]<target && nums[start]<nums[mid]:
end=mid-1
case nums[mid]<target && nums[end]>target && nums[mid]<nums[end]:
start=mid+1
case nums[mid]<nums[start]:
end=mid-1
case nums[mid]>nums[end]:
start=mid+1
case target<nums[start] || target>nums[end]:
return -1
}
}
return -1
}
|
上面的答案分的情况是扁平的，不是很容易理解，下面是通过 if 嵌套来完成的。
- 首先判断
nums[mid]==target的情况，这种情况非常简单，直接 return 即可
- 接着判断
nums[mid]>target的情况，这里需要分情况讨论，也就是需要看 pivot 是在哪里，在 mid 的左边还是在 mid 的右边
- 如果 pivot 在 mid 的左边，也就是
nums[mid]<nums[left]，这种情况下 pivot 并不影响边界的选择，所以可以和没有 pivot 的情况合并
- 如果 pivot 在 mid 的右边，也就是
nums[mid]>nums[right]，这种情况要继续分类讨论
- 如果
target<nums[left]，那么就说明 pivot 将更左边的元素移到了右边去，应该从右边寻找
- 如果
target>nums[left]，就说明 target 还是在 pivot 的左边，就需要从左边寻找
- 最后判断
nums[mid]<target的情况，这里和上面情况类似，可以直接举一个例子来看
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
27
| class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0) return -1;
int left = 0, right = nums.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target) return mid;
if(nums[mid]>target) {
if(nums[mid]>nums[right]) {
if(target<nums[left]) left = mid+1;
else right = mid-1;
}else{
right = mid-1;
}
}else{
if(nums[mid]<nums[left]){
if(target>nums[right]) right = mid-1;
else left = mid+1;
}else{
left = mid+1;
}
}
}
return -1;
}
};
|