题解 | #二分查找-I #旋转数组的最小数字#的Python解法

旋转数组的最小数字

http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

1. 解题思路

拿到这个题的第一反应就是使用min函数不就可以解决（暴力解法）？！于是输入如下代码。

2. 核心代码

复制代码

# -*- coding:utf-8-*-

classSolution:

def minNumberInRotateArray(self, rotateArray):

# write code here

iflen(rotateArray) == 0: #根据题目提示先注意数组大小为0的情况

return0

else:

returnmin(rotateArray) #然后直接用min函数找出最小数字

果真很暴力🤣，而且时间还行！

不过本题不是考这个知识点，所以该解法大家就了解一下。

3. 复杂度分析

时间复杂度： $O(n)$ (n 为数组的长度）
空间复杂度： $O(1)$ (没有额外空间的使用)
-------------------------------------------------我是解法二的分割线---------------------------------------------
4. 解法二

4.1 思路：二分查找

此题其实是要考察二分查找（指每次都跟中间元素值比较大小，然后将待查找区间缩小为之前的一半，直到找到要求的元素值或区间为0）这个知识点。回到本题，我们还是以示例1进行思路的图解。
- 首先初始化分界的左右下标left，right，然后寻找初始中间点下标middle：
- 接着判断最小数字在哪个区间内，进行二分查找：
  - 第一种情况，当中间点的值大于右边界值时：可知最小数字在右区间，此时忽略左区间，右边界下标不变，更新左边界下标。因为中间点是大于最右值的，此时它肯定不是最小值，那么二分后的左边界只会是从 middle + 1 的下标开始，右边界依然是right下标，所以整个区间范围即[middle + 1 , right]；
  - 第二种情况，当中间点的值小于右边界值时：同理可知最小数字在左区间，此时忽略右区间，左边界下标不变，更新右边界下标，即right = middle；
    
    由于示例1此时只剩一个数字，且left下标 == right下标，所以跳出刚刚的循环，直接返回该数字即可。
  - 第三种情况，当中间点的值等于右边界值时：这种情况发生在一个包含重复数字的旋转数组中，看下面这个示例。
    
    此时middle对应值和right 对应值是相等的，那么只有把右边界缩小 1位才能继续进行查找。具体过程如下：
4.2 核心代码
# -*- coding:utf-8 -*-

class Solution:

def minNumberInRotateArray(self, rotateArray):

# write code here

if len(rotateArray) == 0:

return 0

#首先定义最左和最右两个下标变量

left = 0

right = len(rotateArray) - 1

#下面开始二分查找

while left < right:

#首先找到初始中间点，这里用位运算处理更快

middle = left + ((right - left)>> 1)

#下面开始根据最左和最右值与中间值得大小，找最小数字

if rotateArray[middle] > rotateArray[right]:

#当中间值大于最右值时，根据旋转数组定义，此时可知最小值在右区间，所以可以忽略左区间

#由于中间点是大于最右值的，所以中间点一定不是最小值！那么最小值就在中间点右边，所以这里middle+1，更新最左边界下标

left = middle + 1

elif rotateArray[middle] < rotateArray[right]: #当中间值小于最右值，忽略右区间

right = middle #此时只需要更新最右边界下标的位置

else:

right = right - 1 #当中间值等于最右值时，此情况存在于数组中有重复数字的时候：直接右边界下标减一来更新右边界

#当左边界下标 == 右边界下标时，数组只有一个数字就是最小数字，退出循环，直接返回左边界对应值即可

return rotateArray[left]
4.3 复杂度分析
- 时间复杂度： $O(logn)$
  (n 为数组的长度, 大部分情况下都会忽略一半区间；最坏情况下，当数组中元素完全相同时，while会循环n次，这种情况的时间复杂度退化为 $O(n)$ )
- 空间复杂度： $O(1)$ (left, middle, right都使用的是常数大小的空间)