Pythonバイナリメソッドの実装例

1. アルゴリズム: (検索する配列期間を array[low, high] とします)

(1) 周期の中間位置 K を求める
(2) 求めた値 T と array[k] を比較します。それらが等しい場合、検索は成功し、この位置に戻ります。そうでない場合は、新しい検索領域を決定して二分探索を続行します。領域は次のように決定されます:
a.array[k]>T 配列の順序から、array[k,k+1,…,high]>T; したがって、新しい間隔は array[low] になります。 ,… …, K-1]
b.array[k]

2.python コード:

コードをコピー コードは次のとおりです:

#!/usr/bin/python
# -*-コーディング: utf -8 -*-

def BinarySearch(array,t):
low = 0
height = len(array)-1
while low
middle = (low+height)/2
If array[mid]
Low = Mid + 1

elif 配列[mid] > t:
高さ = ミッド - 1

else:
return array[mid]

-1 を返す

if __name__ == "__main__":
print BinarySearch([1,2,3,34,56,57,78,87],57)

結果: 57

3. 時間計算量: O(log2n);

注: 二分探索の前提は、検索するシーケンスが順序どおりである必要があります。