Pythonは二分検索で、整列リストの要素の下付きを検索します.
Pythonは二分検索で、整列リストの要素の下付きを検索します.なぜ二分検索を使用しますか? コード例 whileループにより対応する下付き文字をクエリーでき、要素がリストに存在せずに-1を返すことは、pythonリストに手動でString(文字列)を実現したfindメソッドに相当する.(注:コードは4時間かけて頭を絞って思いついたもので、やはり足りないところがあるに違いない.例えば、サイクルごとにright-left==1を判断する) 再帰的な方法によって–現在、本人は要素がリストにあるかどうかを判断するだけで、whileサイクルのleftとrightの2つの変数を置き換える有効な代替方法が見つからない(あの大物は方法を考えてからコメントして考えを発表することができる)
: !!!!
def BinarySearch(item, list):
'''
:param item:
:param list:
:return: list , -1
'''
end_time = False #
left = 0 # , 0
right = len(list) # ,
while left < right:
if right - left == 1: # right - left == 1
if end_time == True:
return -1 # -1
end_time = True # end_time True,
mid_site = (left + right) // 2
if item == list[mid_site]:
return mid_site #
elif item > list[mid_site]:
left = mid_site # mid_site , mid_site left
else:
right = mid_site # mid_site , mid_site right
if __name__ == '__main__':
list01 = [1, 2, 4, 6, 7, 9, 10, 11, 13]
result01 = BinarySearch(10, list01)
print(result01) # 6 ==> 10 list01 6
result02 = BinarySearch(1000, list01)
print(result02) # -1 ==> 3 list01
def BinarySearch(item, list):
'''
:param item:
:param list:
:return: True, False
'''
# list_length
list_length = len(list)
# 0
if list_length > 0:
#
mid_site = list_length // 2
if item == list[mid_site]: #
return True # True
elif item > list[mid_site]: #
#
# : ,
# mid_site
return BinarySearch(item, list[mid_site + 1:])
else: #
#
# ,
return BinarySearch(item, list[:mid_site])
else:
return False # , False
if __name__ == '__main__':
list01 = [1, 2, 4, 6, 7, 9, 10, 11, 13]
result01 = BinarySearch(9, list01)
print(result01)
result02 = BinarySearch(12, list01)
print(result02)