????????針對序列已經(jīng)排好序了惠窄，以從小到大排好的序列為例，每次取中間的元素和待查找的元素比較漾橙，如果中間的元素比待查找的元素小杆融，就說明“如果待查找的元素存在，一定位于序列的后半部分”霜运，這樣可以把搜索范圍縮小到后半部分脾歇，然后再次使用這種算法迭代。這種“每次將搜索范圍縮小一半”的思想稱為折半查找或二分查找（Binary Search）淘捡。
二分查找的條件是事先經(jīng)過排序藕各，且要求所有備查數(shù)據(jù)都必須加載到內存中進行。
每次變化的都是中間值焦除，這樣每次查找都會比上一次少一半的范圍激况，最多只需要比較log(n)+1次，時間復雜度為O(log(n))。使用二分查找就可以省去一半的遍歷乌逐。
故python實現(xiàn)代碼為
def binarysearch(L,number):
? ? start=0
? ? end=len(L)
? ? while start<=end :? ? ? ? ? ? ? ? ? ? ? ? ? ? #邊界條件范圍縮小到只有一個元素
? ? ? ? mid=(start+end)//2? ? ? ? ? ? ? ? ? ? ? ? #取中間位置
? ? ? ? if L[mid]<number:
? ? ? ? ? ? start=mid+1
? ? ? ? elif L[mid]>number:
? ? ? ? ? ? end=mid-1
? ? ? ? else:
? ? ? ? ? return mid
? ? return -1?
函數(shù)接受一個有序數(shù)組和一個指定查找的元素竭讳。如果該元素包含在數(shù)組中，這個函數(shù)將返回其位置黔帕。而我們所要跟蹤的就是每次要查找的數(shù)組范圍——開始時為整個數(shù)組代咸。
測試用例
>>>binarysearch([1,2,6,8,12,13],6)
2
>>>binarysearch ([1,2,6,8,12,13],7)
-1
>>>?
因為二分查找使用了分治思想，每個子問題的形式和解法都是相同的成黄，因為可以轉化為使用遞歸求解呐芥，如
defrecursionBS(L,number,start,end):
??? if start>end:
??????? return -1
??? mid=(start+end)//2
??? if L[mid]==number:
??????? return mid
??? elif L[mid]>number:
??????? returnrecursionBS(L,number,start,mid-1)
??? else:
??????? return recursionBS(L,number,mid+1,end)
測試用例
>>>recursionBS([1,2,6,8,12,13],6,0,6)
2
>>> recursionBS([1,2,6,8,12,13],8,0,6)
3
>>>recursionBS([1,2,6,8,12,13],1,0,6)
0
>>>recursionBS([1,2,6,8,12,13],13,0,6)
5
