leetcode-33-搜索旋转排序数组
leetcode-33-搜索旋转排序数组
题目描述：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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要完成的函数：
int search(vector<int>& nums, int target)
说明：
1、这道题给定一个vector和一个target整数，vector里面装着一个升序数组，只不过现在这个升序数组在某个节点上旋转了。
比如[4,5,6,7,0,1,2]，原本就是一个升序数组，现在旋转了，要求用O(logn)的时间复杂度找到target在vector中的索引。
比如上面的vector中，给定target为0，那么索引就是4。
如果在vector中找不到target，那么返回-1。
2、这道题不同于以往的整个升序数组，直接二分法就可以找到索引。
不过现在仍然要O(logn)的时间复杂度，那么我们也可以用二分法找到旋转节点的索引，接着判断target在旋转节点的哪边，然后用二分法再次找到target的索引。
代码如下：（附详解）
int search(vector<int>& nums, int target)
{
int s1=nums.size(),front=0,behind=s1-1,med=(behind+front)/2;
if(s1==0)return -1;//如果没有元素，那么返回-1
if(s1==1)//如果只有一个元素，那么判断是不是target的数值
{
if(nums[0]==target)//如果是，那么返回0
return 0;
return -1;//不是就返回-1
}
while(front<behind)//找到旋转节点的索引，最后存储在med中
{
if(nums[front]<nums[behind])//如果front的元素数值小于behind的
{ //那么说明整一段都是升序的
med=front; //那么front就是我们要的旋转节点的索引
break; //这是一个边界条件，看不懂的先看下面的if语句
}
if(nums[med]<nums[med-1]&&nums[med]<nums[med+1])//满足条件，med就是我们要的旋转节点
break;
if(nums[med]>nums[front]||nums[med]>nums[behind])//如果med对应的数值大于front对应的数值
{ //或者med对应的数值大于behind对应的数值
front=med+1; //那么说明旋转节点在med前面
med=(front+behind)/2;
}
else
{
behind=med-1;
med=(front+behind)/2;
}
}
front=0,behind=s1-1;//找到旋转节点的索引之后，我们分两段，看一下target在哪一段
if(nums[front]<=target&&target<=nums[med-1])//用典型的二分法找到target的索引
{
behind=med-1;
while(front<=behind)
{
med=(front+behind)/2;
if(nums[med]==target)
return med;
else if(nums[med]<target)
front=med+1;
else
behind=med-1;
}
return -1;//如果找不到，那么返回-1
}
else if(nums[med]<=target&&target<=nums[behind])//用典型的二分法找到target的索引
{
front=med;
while(front<=behind)
{
med=(front+behind)/2;
if(nums[med]==target)
return med;
else if(nums[med]<target)
front=med+1;
else
behind=med-1;
}
return -1;//如果找不到，那么返回-1
}
return -1;//target没有在旋转节点两边的任何一段之中，那么返回-1
}在通过while循环找到旋转节点的索引的代码中，我们先明确我们要找的旋转节点是“既小于左边的数值，又小于右边的数值”。
比如[4,5,6,7,0,1,2]中，0就是我们要找的旋转节点。
所以判断nums[med]<nums[med-1]&&nums[med]<nums[med+1]这个条件有没有满足，如果满足，那么就是旋转节点。
如果不满足，那么看一下nums[med]会不会大于nums[front]，大于的话那么说明前半段是升序排列，那么旋转节点必然在后半段。
但为什么还要加上nums[med]会不会大于nums[behind]的判断条件呢？
比如[5,1,2,3,4]，这样的vector，第一次循环的时候，front是0，behind是4，med是(0+4)/2=2，此时nums[med]不会大于nums[front]，所以behind变为1，med改变为(0+1)/2=0。
接着进入第二次循环，nums[med]不会大于nums[front]，所以仍然旋转节点在med的前半段吗？但我们知道此时旋转节点应该在med的后半段，也就是为1。
注意到此时med和front都是0，在同一个点上，所以此时可以加上nums[med]跟nums[behind]的比较，来得到一个正确的结论。
有同学可能还会疑惑为什么要在找旋转节点的while循环中，加上nums[front]<nums[behind]的判断？
比如[4,5,6,7,0,1,2]，front为0，behind为6，med为3，也就是元素为7，此时判断旋转节点在后半段。front改变为4，behind仍然为6，med为5。
进入下一个循环，此时front对应元素为0，med为1，behind为2。
我们发现旋转节点的确在[front,behind]的区间中，但是已经不包含任何奇奇怪怪的元素了，整个区间是升序的。
我们也不能再通过nums[med]和nums[front]的比较，或者nums[med]和nums[behind]的比较来得到结论。
此时整个区间升序，那么必然旋转节点在front这里。
上述代码实测4ms，beats 99.75% of cpp submissions。
总结：
这道题的确很繁琐，主要在通过二分法找到旋转节点的索引这一步，要注意各种边界情况的判断，总体抽象的思路也要有。
之后通过二分法找到target的索引这一步，就是典型的二分法操作了，十分容易。