来源：
https://www.cnblogs.com/techflow/p/12441002.html
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做搜索旋转排序数组，我们先来看题面：
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
You are given an integer array nums sorted in ascending order, and an integer target.Suppose that nums 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]).If target is found in the array return its index, otherwise, return -1.
题意
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [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
题解
这题非常明显，虽然看似限制了时间复杂度在提升难度，但其实是在给大家提示。一个数组查找元素，时间复杂度还是log(n)这显然是在暗示大家什么。我想大家作为一个成熟的程序员，异性的暗示未必读的懂，但来自出题人的暗示一定能get到【狗头】。显然，这题需要使用二分法，但是如何使用二分呢，这才是本题的重点。两次二分
第一种方法非常简单粗暴，因为我们已经知道要二分查找了，然后我们还知道数组分成了两截之后又交换了顺序。所以数组的情况应该是这样的：对不起，我画得有些抽象，但是精髓传达到了。什么意思呢？就是原本升序的数组分成了两截之后交换顺序，那么现在的数组应该是两端递增的序列拼接构成的。既然是两端序列，那么中间显然有一个断点。我们只要找到这个断点的位置，就容易了，这个问题就变成了在两个有序的数组里查找元素了，那就没有难度了。显然不是打开QQ音乐，而是要使用二分法。因为前面我们已经说了，我们整体的复杂度是log级的，显然我们不可能用遍历来寻找断点。留给我们的就只有一条路，就是二分。设计这里的二分需要对二分法有一定深入的了解，因为在这个问题当中其实是不满足二分法的使用条件的，因为数组被分成了两个部分，已经不是整体有序了。但是虽然不是整体有序，但仍然是有办法的。我们先来根据上面的图来分析一下，很容易发现，断点的位置就是全局最小值。我们可以找到左侧部分的最大值，或者是右侧部分的最小值，就是断点的位置。我们再来分析一下二分时候可能出现的情况，一开始的时候l在最左侧，r在最右侧，m则是两侧都有可能。如果m在左侧部分，那么m位置的值一定大于l，否则一定小于l。所以我们通过比较m和l位置元素的大小关系可以判断m在左侧还是右侧。如果说我们最终的搜索目标是寻找左侧部分的最大值，那么当m处的值大于l时，则舍弃左侧部分，因为左侧部分已经不可能是答案了。同理，如果m处的值小于l，那么应该舍弃m右侧，因为m右侧都在右边部分，当中是不可能有左侧部分的最大值的，通过这种方法我们也可以使用二分查找，只不过条件和我们常用的二分不太一样。def binary_search(arr):
l, r = 0, len(arr)
while r - l > 1:
m = (l + r) >> 1
if arr[m] > arr[l]:
l = m
else:
r = m
return l
找到断点之后就容易了，就是简单的无脑二分了。我们来看代码：class Solution:
def search(self, nums: List[int], target: int) -> int:
# 找到断点
l, r = 0, len(nums)
if r == 0:
return -1
while r - l > 1:
m = (l + r) >> 1
if nums[m] > nums[l]:
l = m
else:
r = m
# 根据target和第0个元素比较大小判断target在左还是右
if target < nums[0]:
l, r = r, len(nums)
else:
l, r = 0, l+1
if l == len(nums):
return -1
# 二分查找
while r - l > 1:
m = (l + r) >> 1
if nums[m] <= target:
l = m
else:
r = m
return l if nums[l] == target else -1
一次二分
虽然我们三下五除二地解决了问题，但是我仍然不够满意，总觉得这种做法不够巧妙，应该还能继续优化。比如说我们能不能不先找断点的位置直接二分呢？仔细想的话是可以的，尤其是我们已经有了上面这种做法的情况下。在我们上面查找断点的时候，已经有了一个重要的关键信息，就是我们可以通过m和l位置比大小来确定断点在什么位置。既然我们可以确定断点的位置，那么我们同样可以确定target的位置。这是一种情况，即m的位置在断点右侧，也就是右侧。那么我们通过判断target和l处的大小关系可以判断target可能在哪个部分。如果target > nums[l]，那么显然target在左侧，所以我们应该让r=m，即抛弃右部分。如果target < nums[l]，这个时候还不能确定范围。因为m左侧可能还有比m小的元素，所以我们还需要判断一下target和nums[m]的关系，来判断抛弃哪个部分。如果target < nums[m]，那么抛弃右部分，否则抛弃左部分。同样我们判断target和nums[l]的关系，如果target > nums[l]，那么我们需要继续判断它和m的关系，来决定抛弃哪个部分。如果target < nums[l]，那么说明我们需要抛弃m左侧的部分。情况虽然有点复杂，但是我们画个图还是很容易理清楚的。一旦理清楚了，我们就可以一次二分搞定全局。class Solution:
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return -1
l, r = 0, len(nums)
while r - l > 1:
m = (l + r) >> 1
# 如果m出现做左侧部分
if nums[m] >= nums[l]:
if target >= nums[l]:
if target < nums[m]:
r = m
else:
l = m
# 如果target小于nums[l]，需要让l=m+1，因为m这个点也是非法点
else:
l = m+1
else:
if target >= nums[l]:
r = m
else:
if target >= nums[m]:
l = m
else:
r = m
return l if l < len(nums) and nums[l] == target else -1
到这里整个题目就分析完了，但是比较搞笑的是虽然我们第二种算法看起来牛哄哄，减少了一次二分，但是提交上去之后的结果反而耗时要长一些。而且相信大家也感觉到了，这种方法实现起来要复杂得多，边界条件很容易写错。所以这点告诉我们一个道理，厉害的方法不一定效果好。这道题虽然不难，但是挺有意思，打破了我们一直以来对于二分法的认识，不知道会不会给你们带来脑洞大开的感觉。好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
