HOWTO · Python
Python 二叉搜索
本教程演示了如何在 Python 中使用二叉搜索算法。
本页内容
注意
如果你想详细了解二叉搜索，那么可以参考二叉搜索算法一文。
二叉搜索算法
假设我们有一个未排序的数组 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
