搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
在做这个题之前，我们首先来学习一下二分
二分查找
当我们要从一个序列中查找一个元素的时候，最快想到的方法就是暴力查找法（即：从前到后依次查找）。但这种方法过于无脑，适用于元素较少的时候，一旦元素个数多起来，效率是非常低下，所以在实际中这种查找的方法是被摒弃的。
这里就不得不介绍一种简单且效率较高的查找方法了：二分查找法，又称折半查找法。但该方法是建立在有序的前提下的。
二分查找法的前提条件是：查找的序列必须是有序的。即该序列中的所有元素都是按照升序或者降序排列好的，元素与元素只间的差值虽然是随机的，但始终是在递增或递减。
int check(int num[],int size,int t){
int left=0,right=size-1; // 定义了t在左闭右闭的区间内，[left, right]
while(left<=right){ //当left==right时，区间[left, right]仍然有效
int mid=left+((right-left)/2);//等同于(left+right)/2，防止溢出
if(num[mid]>t){
right=mid-1; //t在左区间，所以答案在[left, mid-1]
}else if(num[mid]<t){
left=mid+1; //t在右区间，所以答案在[mid+1,right]
}else{ //num[mid]==t，找到答案
return mid;
}
}
return -1; //没有找到目标值
}简单的学习了一下二分我们来看接下来这道题：
对于有序数组，可以使用二分查找的方法查找元素。
但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。
可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。
这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：
如果 [l, mid – 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid – 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 [nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid – 1] 中寻找。
参考答案如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
//二分查找
int l=0,r=nums.size()-1;
if(r==0)return nums[0]==target?0:-1;
while(l<=r){
int mid=(l+r)/2;
if(target==nums[mid])return mid;
//判断升降序
if(l<=mid&&nums[l]<=nums[mid]){
//左半部分有序
if(target>=nums[l]&&target<nums[mid]){
r=mid-1;
}else{
l=mid+1;
}
}else{
//右半部分有序
if(target>nums[mid]&&target<=nums[r]){
l=mid+1;
}else{
r=mid-1;
}
}
}
return -1;
}
};
今天的更新就到这里，如有错误欢迎指出，谢谢大家
