旋转数组的最小数字，二分查找法和详细题解思路分析

题目描述这道题最直观的解法并不难，从头到尾遍历数组一次，就能找到最小的元素，时间复杂度为O(n)。但是这个思路没有利用到输?的旋转数组的特性，在有序数组中用二分查找法可以实现O(logn)的查找。我们注意到，旋转之后的数组实际上可以分为两个有序的子数组，而且前面的子数组的元素都大于等于后面子数组中的元素，此外，我们还注意到这个最小的元素正好是两个子数组的分界线。因为，我们可以尝试用二分查找的思路来寻找这个分界点。同二分查找算法的思路，定义两个指针index1和index2，初始分别指向数组的第一个元素和最后一个元素。
计算得到数组中间元素的下标indexMid=(index1+index2)2，判断该中间元素与第一个元素和最后一个元素的大小关系。
如果该中间元素属于前面的递增子数组，那么它应该大于等于index1指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第?个指针index1指向该中间元素，缩小寻找的范围，移动之后的第?个指针仍然位于前面的递增子数组中。
反之，如果该中间元素属于后面的递增子数组，那么它应该小于等于index2指向的元素。此时数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针index2指向该中间元素，缩小寻找的范围，移动之后的第二个指针仍然位于后面的递增子数组中。
这样一来，不管是移动index1还是index2，查找范围都会缩小一半，然后我们再用更新后的两个指针，重复上述过程。
最终，第一个指针index1将指向前面递增子数组的最后一个元素，第二个指针index2会指向后面递增子数组的第一个元素，也即它们会指向两个相邻的元素。此时，第二个指针指向的正好就是分界点，即数组中最小的元素。这是循环结束的条件。
特例一：如果是把递增数组的前面0个元素搬到末尾，即数组本身，这仍然是数组的?个旋转，此时，数组中的第一个元素即为最小元素，直接返回即可。为了处理这种情况，我们可以把indexMid初始化为index1，一旦发现第一次循环就有数组第一个数字numbers[index1]<最后一个数字numbers[index2]，说明该数组本身已是递增的，直接返回第一个元素numbers[indexMid]也就是numbers[index1]。
特例二：当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间元素是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，只能退化为顺序查找的方法。
Python
classSution(object):
defminArray(self,numbers):
"""
:tyenumbers:List[int]
:rtye:int
"""
iflen(numbers)==0:turnNone#顺序查找函数
deffindMinInOrder(left,right):
s=numbers[left]
foriinrange(left,right+1):
ifnumbers[i]<s:
s=numbers[i]
turnsindex1=0
index2=len(numbers)-1
indexMid=index1#初始化为index1的原因是考虑到数组已是有序的情况
whilenumbers[index1]>=numbers[index2]:#?旦发现数组中第?个数字?于最后?个数字，表明该数组已是排好序的，直接返回第一个元素
ifindex2-index1==1:#循环结束条件，两个指针指向两个相邻的元素，此时第二个指针指向的即为分界点。
indexMid=index2
eak
indexMid=(index1+index2)2#向下取整#当下标为index1，index2，indexMid指向的三个数字相等，则无法判断中间的数字是位于前?的?数组中还是后?的?数组中，
#也就无法移动指针进一步缩小查找范围，不得不退化为顺序查找
ifnumbers[indexMid]==numbers[index1]andnumbers[indexMid]==numbers[index2]:
turnfindMinInOrder(index1,index2)ifnumbers[indexMid]>=numbers[index1]:#indexMid处于左边的递增子数组中，那么分界点一定位于它后面，更新左边界缩小查找范围
index1=indexMid
ifnumbers[indexMid]<=numbers[index2]:#indexMid处于右边的递增子数组中，那么分界点一定位于它前面，更新右边界缩小查找范围
index2=indexMidturnnumbers[indexMid]Java
classSution{
ubcintminArray(int[]numbers){
intleft=0;
intright=numbers.length-1;
intmid=left;
while(numbers[left]>=numbers[right]){
if(right-left==1){循环结束条件
mid=right;此时第二个指针指向的元素即为最小元素
eak;
}
mid=(left+right)2;
if(numbers[left]==numbers[mid]&am;&am;numbers[mid]==numbers[right]){
turnfindInOrder(numbers,left,right);三者相同时，采用顺序查找
}
if(numbers[mid]>=numbers[left])中间元素属于前面子数组，最小元素位于该中间元素的后面
left=mid;
if(numbers[mid]<=numbers[right])中间元素属于后面子数组，最小元素位于该中间元素的前面
right=mid;
}
turnnumbers[mid];
}ubcintfindInOrder(int[]numbers,intleft,intright){
ints=numbers[left];
for(inti=0;i<=right;i++){
if(numbers[i]<s)
s=numbers[i];
}
turns;
}
}