当前位置 博文首页 > guoziqing506的博客：寻找旋转排序数组中的最小值
题目描述：假设一个旋转排序的数组其起始位置是未知的（比如：0 1 2 4 5 6 7 可能变成是：4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假设数组中不存在重复的元素。
样例：给出[4,5,6,7,0,1,2] ?返回 0
从本质上讲，跟排序数组中查找target是一个道理。但是有两点不同：（1）是一个经过旋转的排序数组。（2）找的是最小的元素
首先，我们可以把一个排序数组先分割成两部分[first, second]，其中，first代表前面几个元素，second代表之后的，例如，对于数组[0, 1, 2, 4, 5, 6, 7]，可以设定first = [0, 1, 2], second = [4, 5, 6, 7]. 那么，经过旋转之后，数组就变成了[second, first]，我们观察一下，这个新数组有这样两个特性：（1）second中所有元素都大于first中任意元素（2）second与first都是递增的序列
那么，我们的目标很明确了：寻找second的第一个元素。还是用二分法（关于二分查找的基础介绍，详见：点击打开链接），代码如下：
class Solution:
# @param num: a rotated sorted array
# @return: the minimum number in the array
def findMin(self, num):
left, right = 0, len(num) - 1
while left < right and num[left] > num[right]:
mid = (left + right) // 2
# mid指在second中
if num[left] <= num[mid]:
left = mid + 1
# mid指在first中
elif num[left] > num[mid]:
right = mid
return num[left]
# write your code here这里，循环的条件增加了一个：num[left] > num[right]，目的是为了让循环中left始终指向second中的元素，同时，对于未旋转的数组，使其一开始就不进入循环。而left < right的条件设定，则是为了让left始终和right不指向同一个元素。
循环中，通过比较num[left]与num[mid]的值来判断mid所在的位置，不断逼近first的第一个元素。最后，left会指向second之后的第一个元素，也就是first的第一个元素，循环也就在此时结束。
总结来说，就是二分查找，但是对于数组边界的处理需特别小心。
