算法教程 - 二分查找

二分查找是一种在有序数组中查找特定元素的搜索算法。它通过每次将搜索范围减半来提高搜索效率。

基本原理

1. 初始化：设置两个指针，一个指向数组的开始位置（left），另一个指向数组的结束位置（right）。
2. 循环：当 left 小于等于 right 时，执行以下步骤：
   • 计算中间位置 mid：mid = left + (right - left) / 2
   • 比较中间位置的元素与目标值：
     • 如果中间位置的元素等于目标值，则查找成功。
     • 如果中间位置的元素小于目标值，则将 left 指针移动到 mid + 1。
     • 如果中间位置的元素大于目标值，则将 right 指针移动到 mid - 1。
3. 结束：当 left 大于 right 时，查找失败。

代码示例

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

扩展阅读

更多关于算法教程的内容，请访问算法教程首页。

图片展示