题目描述
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
解题思路
- 参考博客园博客
- 这道题让在旋转数组中搜索一个给定值，若存在返回坐标，若不存在返回 -1。我们还是考虑二分搜索法，但是这道题的难点在于不知道原数组在哪旋转了，还是用题目中给的例子来分析，对于数组 [0 1 2 4 5 6 7] 共有下列七种旋转方法（红色表示中点之前或者之后一定为有序的）：
0 1 2 4 5 6 7 7 0 1 2 4 5 6 6 7 0 1 2 4 5 5 6 7 0 1 2 4 4 5 6 7 0 1 2 2 4 5 6 7 0 1 1 2 4 5 6 7 0
二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段，观察上面红色的数字都是升序的，可以得出出规律，
- 如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了，代码如下：
- 其实最主要的是 begin end的范围 这一步最主要的是 去掉一半不可能在的位置里
class Solution {
public:
int search(vector<int>& nums, int target) {
int begin = 0;
int end = nums.size() - 1;
while(begin <= end){
int mid = (begin + end) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] < nums[end]){
if(nums[mid] < target && nums[end] >= target){
begin = mid + 1; // 其实最主要的是 begin end的范围 这一步最主要的是 去掉一半不可能在的位置里
}else{
end = mid - 1;
}
}else{
if(nums[mid] > target && nums[begin] <= target){
end = mid - 1;
}else{
begin = mid + 1;
}
}
}
return -1;
}
};
