题目描述
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.
在一个旋转有序数组里查找某个元素的位置，如果没有这个元素返回-1，这个数组里没有重复元素
代码及注释
class Solution {
public:
int search(vector<int>& nums, int target) {
// 线性表搜索问题一般都会用到二分法
// 二分法涉及三个指针min max mid
int min = 0, max = nums.size()-1;
// 二分法最终的停止条件
while(min <= max){
// 初始第一次二分的mid
int mid = (min+max)/2;
// 如果mid恰好是target(最终target都会到mid这里)
if(nums[mid] == target) return mid;
// 如果左半部分有序,则在此半部分（有序字符串）进行二分查找
if(nums[min] <= nums[mid]){
if(nums[min]<=target && target<nums[mid])
max = mid - 1;
else
min = mid + 1;
}
// 如果右半部分有序
else{
if(nums[mid]< target && target<=nums[max])
min = mid + 1;
else
max = mid - 1;
}
}
// 不满足最高二分条件min<=max时
return -1;
}
};
二分法大体框架
// 二分法前提是用在有序数组，并且要注意二分法的停止条件以及大体框架
// 二分法最终return的都是mid
// 注意几次等号边界，target和mid第一处if等号，其余都不等
left = 0; right = size - 1;mid = 0;
while(left <= right){
if(N[mid] == target)
return mid;
if(N[left] <= target && target< N[mid]){
right = mid - 1;
}
else{
right = mid + 1
}
}
分析
