Python 二叉搜索

  2. 贴士文章
  3. Python 贴士
  4. Python 二叉搜索
Harshit Jindal 2023年1月30日 2021年2月28日
Python Python Algorithm
  1. 二叉搜索算法
  2. 二叉搜索的 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
Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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

相关文章 - Python Algorithm