搜索旋转数组

欢迎大家阅读我的博客，给生活加点impetus！！

让我们进入《题海探骊》，感受算法之美！！

搜索旋转数组

题目链接

在线OJ

题目详解

注意：
1：算法复杂度为 O（log^n)
2:nums数组升序排列

在这里，你可能会想到有一个题叫旋转数组，那道题的思路是新建一个数组，循环遍历原数组，利用nums[(i+k)%numsSize],将对应位置的旧数组元素放入到新数组中，但是循环遍历的话时间复杂度就是O（n），有兴趣的话可以做一下旋转数组，那这里我们如何解决时间复杂度呢？，解决了时间复杂度之后，旋转数组不一定有序，我们该如何遍历呢？

解题思路

双指针(二分法遍历)

首先是时间复杂度，我们可以利用二分法，此方法的时间复杂度刚好满足O(log^n)，但是使用的前提是有序，前面也提到，旋转数组不一定有序，但是，如果按照最坏的情况来看，旋转数组有两个区间段是有序地，那么如何来区分这两个区间段呢？就是要找最小的数据，进而得到最小数据的下标

所以：

找最小数据的下标分段并返回下标i->两段分别用二分法遍历->找到并返回下标，没找到返回-1

那我们二分法遍历的依据是什么？最原始的二分法是以mid和target的大小来缩小查找范围的。

这里的依据是target与nums[numsSize-1]的大小比较划分区域

第一种：target>nums[numsSize−1]，那么target一定在第一段[0,i−1]中，在[0,i−1]中二分查找target。

第二种：target≤nums[numsSize−1]，那么：
如果i=0，说明nums是递增的，直接在[0,n−1]中二分查找target。
如果i>0，那么target一定在第二段[i,numsSize−1]中，在[i,numsSize−1]中二分查找target。
这可以看成：在[i,numsSize−1]中二分查找target。

代码实现

我们先来实现找最小数据的下标：

为什么要令left=-1，我们来例举看下面一种情况：

为什么需要mid来left+（right-left）/2呢？

为了防止栈溢出。

因为有两个区间需要遍历，我们将这里的二分法封装为一个函数：

这里是调整mid加减1来放置死循环，也是可以的。
大于nums[mid]，缩左边，小于nums[mid],缩右边。

最后，我们再来看主代码：

注意特殊的情况：一开始直接就是升序的，此时传递参数就要注意防止越界访问

结语

感谢大家阅读我的博客，希望你会有更好的思路与我交流，不足之处欢迎指正！！逆水行舟–不进则退！！加油！！