二分查找定義
二分查找，又稱折半查找，是對一組有序的數(shù)字進行查找腹忽，其思想如下：
- 將待查的數(shù)據(jù)x與數(shù)字的中值mid進行比較，如相等則查找成功砚作，返回x在arr中的索引窘奏；若x>mid，則執(zhí)行2葫录；若x<mid着裹，則執(zhí)行3
- 只檢查右邊的數(shù)據(jù)，重復1米同，直到arr下標low>=high時結(jié)束
- 只檢查左邊的數(shù)據(jù)骇扇，重復1，直到arr下標low>=high時結(jié)束
遞歸實現(xiàn)
import time
# 二分查找（遞歸實現(xiàn)）
def binarySearch(arr, low, high, x):
'''
該函數(shù)用于實現(xiàn)二分查找
:param arr: 存儲數(shù)據(jù)的數(shù)組
:param low: 第一個元素的下標
:param high: 最后一個元素下標
:param x: 待查找的數(shù)據(jù)
:return: mid面粮，數(shù)據(jù)所在的索引
'''
if low <= high:
mid = int((low + high) / 2)
if x == arr[mid]:
# 返回索引
return mid
# 元素小于中間位置元素少孝，只需要再比較左邊的元素
if x < arr[mid]:
return binarySearch(arr, low, mid - 1, x)
# 元素大于中間位置元素，只需要再比較右邊的元素
if x > arr[mid]:
return binarySearch(arr, mid + 1, high, x)
else:
return -1
# 測試數(shù)組
arr = ['a', 'b', 'c', 'd']
x = '1'
# 開始時間
start = time.clock()
# 函數(shù)調(diào)用
result = binarySearch(arr, 0, len(arr) - 1, x)
# 結(jié)束時間
end = time.clock()
# 輸出
if result != -1:
print('元素在數(shù)組中的索引為：{}'.format(result))
else:
print('元素不在數(shù)組中熬苍！')
# 輸出函數(shù)運行的時間
print(end - start)
非遞歸實現(xiàn)
# python非遞歸實現(xiàn)二分查找
def BinarySearch(arr, low, high, x):
while True:
if low <= high:
mid = int((low + high) / 2)
if arr[mid] == x:
return mid
elif x < arr[mid]:
high = mid - 1
else:
low = mid + 1
else:
return -1
# 測試數(shù)組
arr = [1, 2, 3, 4, 5, 6, 7, 8]
x = 10
# 調(diào)用函數(shù)
index = BinarySearch(arr, 0, len(arr) - 1, x)
# 輸出結(jié)果
print('{x}在arr中的索引為{index}'.format(x=x, index=index))
注意本文在遞歸與非遞歸方法中稍走，mid的取值公式mid = int(low + high) / 2，這里相當于是向下去取整了冷溃，即當arr = [1,2,3,4,5,6,7,8]時钱磅，low = 0，high = 7似枕，此時，mid = int((0 + 7) / 2) = int(3.5) = 3年柠，所以第一輪的比較是x與4進行比較凿歼，若此時x>4，則下一輪的比較則會變成x與6進行比較了冗恨，因為我們是向下取整答憔，所以選的是6
補充
- Python中
math模塊有專用的向下向上取整函數(shù)，以下以代碼示例給出：
import math
f = 5.63
# 向上取整
print(math.ceil(f))
# 向下取整
print(math.floor(f))
# 四舍五入
print(round(f))
# 向下取整返回的類型
print(type(math.floor(f)))
執(zhí)行結(jié)果
image.png
可以看到掀抹，取整函數(shù)返回的結(jié)果的類型是
int虐拓，因此，上式mid = int(low + high) / 2也可以換成mid = math.floor((low + high) / 2)
- 二分查找的關鍵在于
mid = int(low + high) / 2傲武，正式因為這個式子蓉驹，我們才可以每次都從中間取一個數(shù)城榛。根據(jù)實際情況，我們也可以修改該式子态兴，比如：mid = int(low + high) / 3狠持，mid取值方式不同，算法的性能也可能不同
