題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。
解題思路：看到這道題首先的樸素想法是依次遍歷數(shù)組，然后將最小數(shù)字得出，但是顯然這種算法沒有用到旋轉(zhuǎn)數(shù)組的特性，因此需要進一步考慮。題目中給出的數(shù)組是一定程度上有序的，因此考慮運用二分查找法來解決這道考題。
思考如下：
1.首先考慮一般的過程，對于一個部分有序的數(shù)組，首先指定兩個指針將p1指定為首指針，p2指定為尾指針，然后指定mid指針，可以將旋轉(zhuǎn)數(shù)組看成兩個遞增的子數(shù)組，mid為首尾指針的中間位置，如果p1位置的元素大于等于p2位置的元素，此時進行判斷：
①如果mid位置的元素大于或者等于p1指針對應(yīng)位置的元素，則說明其元素屬于第一個遞增數(shù)組，將p1指針移動到mid位置，縮小搜索最小數(shù)字的范圍，然后繼續(xù)；
②如果mid位置的元素小于或者等于p2指針對應(yīng)位置的元素 ，則說明其元素屬于第二個遞增數(shù)組，將p2指針移動到mid位置，說明對應(yīng)的最小數(shù)字在mid位置前面的元素中；
結(jié)束條件 ：p2-p1==1，即兩個指針相鄰，說明p1為第一個遞增子數(shù)組的最后一個元素位置，p2為第二個子數(shù)組的第一個元素，則返回最小的數(shù)字為p2位置對應(yīng)的元素。
2.特殊情況：
如果將首位的0個元素放到后面，即原數(shù)組也是其中的一個旋轉(zhuǎn)數(shù)組，此時p1位置的元素小于p2位置的元素，因此如果一開始首位的元素小于末尾的元素說明這是一個遞增的數(shù)組，故最開始賦值的時候?qū)id賦值為p1即可。因為不滿足循環(huán)條件會直接返回mid元素。
特殊情況2:如果mid==p1==p2對應(yīng)位置的元素，則無法再縮小搜索范圍，因此需要按照順序進行查找最小的元素。
代碼實現(xiàn)：
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray)<= 0:
return 0
p1 = 0
p2 = len(rotateArray)-1
mid = p1
while rotateArray[p1] >= rotateArray[p2]:
mid = int((p1+p2)/2)
if rotateArray[p1] == rotateArray[mid] and rotateArray[p2]==rotateArray[mid]:
return self.Findmin(rotateArray,p1,p2)
if p2-p1 == 1:
mid = p2
break
if rotateArray[mid] >= rotateArray[p1]:
p1 = mid
elif rotateArray[mid] <= rotateArray[p2]:
p2 = mid
return rotateArray[mid]
def Findmin(self,rotateArray,p1,p2):
result = rotateArray[p1]
for i in range(p1+1,p2+1):
if rotateArray[i] < result:
result = rotateArray[i]
return result
結(jié)果：
