LeetCode 33，在不满足二分的数组内使用二分的方法
TechFlow2019 人气:0
本文始发于个人公众号：**TechFlow**，原创不易，求个关注
## 链接 [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array)
## 难度 Medium
## 描述
给定一个升序排列的数组，它被**分成两部分之后交换了顺序**。要求给定一个元素，返回这个元素的在数组当中的下标，如果不存在返回-1. 时间复杂度必须是$O(logn)$ 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. Your algorithm's runtime complexity must be in the order of _O_ (log _n_ ).
**样例 1:** Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 **样例 2:** Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
## 题解
这题非常明显，虽然看似限制了时间复杂度在提升难度，但其实是在给大家提示。一个数组查找元素，时间复杂度还是$log(n)$，这显然是在暗示大家什么。我想大家作为一个成熟的程序员，异性的暗示未必读的懂，但来自出题人的暗示一定能get到【狗头】。 显然，这题需要使用二分法，但是如何使用二分呢，这才是本题的重点。
## 两次二分
第一种方法非常简单粗暴，因为我们已经知道要二分查找了，然后我们还知道数组分成了两截之后又交换了顺序。所以数组的情况应该是这样的：  对不起，我画得有些**抽象**，但是精髓传达到了。什么意思呢？就是原本升序的数组分成了两截之后交换顺序，那么现在的数组应该是两端递增的序列拼接构成的。既然是两端序列，那么**中间显然有一个断点**。我们只要找到这个断点的位置，就容易了，这个问题就变成了在两个有序的数组里查找元素了，那就没有难度了。 但是这个断点怎么找呢？ 显然不是打开QQ音乐，而是要使用**二分法**。因为前面我们已经说了，我们整体的复杂度是log级的，显然我们不可能用遍历来寻找断点。留给我们的就只有一条路，就是二分。 设计这里的二分需要对二分法有一定深入的了解，因为在这个问题当中其实是**不满足二分法的使用条件**的，因为数组被分成了两个部分，已经不是整体有序了。但是虽然不是整体有序，但仍然是有办法的。 我们先来根据上面的图来分析一下，很容易发现，断点的位置就是全局最小值。我们可以找到左侧部分的最大值，或者是右侧部分的最小值，就是断点的位置。 我们再来分析一下二分时候可能出现的情况，一开始的时候l在最左侧，r在最右侧，**m则是两侧都有可能**。如果m在左侧部分，那么m位置的值一定大于l，否则一定小于l。所以我们通过比较m和l位置元素的大小关系可以判断m在左侧还是右侧。 如果说我们最终的搜索目标是寻找左侧部分的最大值，那么当m处的值大于l时，则舍弃左侧部分，因为左侧部分已经不可能是答案了。同理，如果m处的值小于l，那么应该舍弃m右侧，因为m右侧都在右边部分，当中是不可能有左侧部分的最大值的，通过这种方法我们也可以使用二分查找，只不过条件和我们常用的二分不太一样。 ```python 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 ``` 找到断点之后就容易了，就是简单的无脑二分了。我们来看代码： ```python 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左侧的部分。 情况虽然有点复杂，但是我们画个图还是很容易理清楚的。一旦理清楚了，我们就可以一次二分搞定全局。 来看代码： ```python 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 ``` 到这里整个题目就分析完了，但是比较搞笑的是虽然我们第二种算法看起来牛哄哄，减少了一次二分，但是提交上去之后的结果反而**耗时要长一些**。而且相信大家也感觉到了，这种方法实现起来要复杂得多，边界条件很容易写错。所以这点告诉我们一个道理，厉害的方法不一定效果好。 这道题虽然不难，但是挺有意思，打破了我们一直以来对于二分法的认识，不知道会不会给你们带来脑洞大开的感觉。 今天的文章就是这些，如果觉得有所收获，请顺手点个**关注**吧，你们的举手之劳对我来说很重要。 
## 链接 [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array)
## 难度 Medium
## 描述
给定一个升序排列的数组，它被**分成两部分之后交换了顺序**。要求给定一个元素，返回这个元素的在数组当中的下标，如果不存在返回-1. 时间复杂度必须是$O(logn)$ 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. Your algorithm's runtime complexity must be in the order of _O_ (log _n_ ).
**样例 1:** Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 **样例 2:** Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
## 题解
这题非常明显，虽然看似限制了时间复杂度在提升难度，但其实是在给大家提示。一个数组查找元素，时间复杂度还是$log(n)$，这显然是在暗示大家什么。我想大家作为一个成熟的程序员，异性的暗示未必读的懂，但来自出题人的暗示一定能get到【狗头】。 显然，这题需要使用二分法，但是如何使用二分呢，这才是本题的重点。
## 两次二分
第一种方法非常简单粗暴，因为我们已经知道要二分查找了，然后我们还知道数组分成了两截之后又交换了顺序。所以数组的情况应该是这样的：  对不起，我画得有些**抽象**，但是精髓传达到了。什么意思呢？就是原本升序的数组分成了两截之后交换顺序，那么现在的数组应该是两端递增的序列拼接构成的。既然是两端序列，那么**中间显然有一个断点**。我们只要找到这个断点的位置，就容易了，这个问题就变成了在两个有序的数组里查找元素了，那就没有难度了。 但是这个断点怎么找呢？ 显然不是打开QQ音乐，而是要使用**二分法**。因为前面我们已经说了，我们整体的复杂度是log级的，显然我们不可能用遍历来寻找断点。留给我们的就只有一条路，就是二分。 设计这里的二分需要对二分法有一定深入的了解，因为在这个问题当中其实是**不满足二分法的使用条件**的，因为数组被分成了两个部分，已经不是整体有序了。但是虽然不是整体有序，但仍然是有办法的。 我们先来根据上面的图来分析一下，很容易发现，断点的位置就是全局最小值。我们可以找到左侧部分的最大值，或者是右侧部分的最小值，就是断点的位置。 我们再来分析一下二分时候可能出现的情况，一开始的时候l在最左侧，r在最右侧，**m则是两侧都有可能**。如果m在左侧部分，那么m位置的值一定大于l，否则一定小于l。所以我们通过比较m和l位置元素的大小关系可以判断m在左侧还是右侧。 如果说我们最终的搜索目标是寻找左侧部分的最大值，那么当m处的值大于l时，则舍弃左侧部分，因为左侧部分已经不可能是答案了。同理，如果m处的值小于l，那么应该舍弃m右侧，因为m右侧都在右边部分，当中是不可能有左侧部分的最大值的，通过这种方法我们也可以使用二分查找，只不过条件和我们常用的二分不太一样。 ```python 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 ``` 找到断点之后就容易了，就是简单的无脑二分了。我们来看代码： ```python 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左侧的部分。 情况虽然有点复杂，但是我们画个图还是很容易理清楚的。一旦理清楚了，我们就可以一次二分搞定全局。 来看代码： ```python 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 ``` 到这里整个题目就分析完了，但是比较搞笑的是虽然我们第二种算法看起来牛哄哄，减少了一次二分，但是提交上去之后的结果反而**耗时要长一些**。而且相信大家也感觉到了，这种方法实现起来要复杂得多，边界条件很容易写错。所以这点告诉我们一个道理，厉害的方法不一定效果好。 这道题虽然不难，但是挺有意思，打破了我们一直以来对于二分法的认识，不知道会不会给你们带来脑洞大开的感觉。 今天的文章就是这些，如果觉得有所收获，请顺手点个**关注**吧，你们的举手之劳对我来说很重要。 
加载全部内容