Python 二叉搜尋
Harshit Jindal
2023年1月30日
2021年2月28日
注意
如果你想詳細瞭解二叉搜尋，那麼可以參考二叉搜尋演算法一文。
二叉搜尋演算法
假設我們有一個未排序的陣列 A[]，包含 n 個元素，我們想找到一個元素 X。
-
設
lo為0，hi為n - 1。 -
當
lo<hi時，設mid=lo + (hi - lo)/2。- 如果
A[mid]==X，我們找到了元素，返回索引mid。 - 如果
A[mid]<X，則丟棄左半部分元素，並設定lo為mid+1。 - 如果
A[mid]>X，則丟棄右半部分元素，並將hi設為mid-1。
- 如果
-
沒有找到元素，所以返回
-1。
二叉搜尋的 Python 程式
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [ 2, 3, 4, 1, 5 ]
x = 4
n = len(arr)
result = binary_search(arr, x ,n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
輸出：
Element is present at index 2
Author: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn