在 Python 中分別用循環(huán)和遞歸兩種方式來實現(xiàn)二分查找法
本文的最新版本位于：https://github.com/iwhales/algorithms_notes
轉(zhuǎn)載請注明出處：http://www.reibang.com/u/5e6f798c903a
# -*- coding: utf-8 -*-
# 二分查找的時間復(fù)雜度是math.log(n,2)
def binary_search_loop(a_list: list, item: int):
"""
循環(huán)方式
:param a_list: 有序列表
:param item: 被查找的目標(biāo)項
:return: 如果a_list中包含item识虚，返回item的索引值盆昙，否則返回None
"""
low = 0
high = len(a_list) - 1
while low <= high:
mid = (low + high) // 2
guess = a_list[mid]
if guess == item:
return mid
elif guess > item:
high = mid - 1
else:
low = mid + 1
return None
def binary_search_recursive(a_list: list, item: int):
"""
遞歸方式
:param a_list: 有序列表
:param item: 被查找的目標(biāo)項
:return: 如果a_list中包含item它呀，返回item的索引值，否則返回None
"""
mid = (len(a_list) - 1) // 2
if len(a_list) == 1:
if item == a_list[0]:
return 0
else:
return None
if item == a_list[mid]:
return mid
elif item > a_list[mid]:
index = binary_search_recursive(a_list[mid + 1:], item)
if index is None:
return None
return mid + 1 + index
else:
index = binary_search_recursive(a_list[:mid], item)
return index
if __name__ == '__main__':
my_list = [1, 2, 3, 4]
assert binary_search_loop(my_list, 1) == 0
assert binary_search_loop(my_list, 2) == 1
assert binary_search_loop(my_list, 3) == 2
assert binary_search_loop(my_list, 4) == 3
assert binary_search_loop(my_list, 10) is None
assert binary_search_recursive(my_list, 1) == 0
assert binary_search_recursive(my_list, 2) == 1
assert binary_search_recursive(my_list, 3) == 2
assert binary_search_recursive(my_list, 4) == 3
assert binary_search_recursive(my_list, 10) is None
