Python實現二分查找
為什么需要二分查找
-
如果查找1-100內任意一個數字？
-
順序查找（簡單查找）
從1開始或者100倒著來進行查找
最快只需要一次，但是最慢則需要一百次蛉顽，差距相當大
大O表示法為 O(n)
-
二分查找
每次從中間進行查找尤筐，先從50，再判斷大還是小日熬，再從75或者25進行查找棍厌，依次類推
由于每次都會排除一般的數字，所以最慢也只需要7次竖席，log2 n次
大O表示法為O(log n)
要求：必須是有序的情況
-
從上面的例子可以看出來耘纱，在有序的情況下，二分查找的效率是很高的
大O表示法
大O表示法是一種比較特殊的表示法毕荐，指出了算法的消耗時間速度束析，主要可以表示兩種算法之間時間消耗的不同增速
小明要準備去北京玩，為了更好的準備东跪，小明提前準備了100套線路方案畸陡，然后準備用程序驗證那種方案更加方便省時間鹰溜，如果使用簡單查找的話進行驗證，假設一套方案需要一秒鐘丁恭，那么100套就需要100毫秒(O(n)曹动，而使用二分查找的話只需要7毫秒(O(log n)，這就整整差了十多倍的時間牲览，這僅僅只是100套墓陈，如果是一億套方案呢，簡單查找時間就會更久, 由此我們可以根據大O表示法比較兩個算法直接的時間增量速度以此判斷哪個算法更加便捷
python代碼實現二分查找
def BinarySearch(list1, num):
min = 0 # 最小的下標
max = len(list1) - 1 # 最大的下標
i = 0
while True:
i += 1
mid = (max + min) // 2 # 中間的下標每次向下取整
if num > list1[mid] :
min = mid + 1 # 小于需要的猜的數第献，則將最小下標變?yōu)橹虚g的贡必，又因為中間的已經猜過，所以要加1
elif num == list1[mid] :
print("找到數據")
print("一共查找%d次"%i)
break
else :
max = mid - 1 # 大于需要的猜的數庸毫，則將最大下標變?yōu)橹虚g的仔拟，又因為中間的已經猜過，所以要減1
if __name__ == "__main__":
list1 = [i for i in range(0,100)]
num = 5
BinarySearch(list1, num)
