学习二分法查找的Python技巧

什么是二分法查找

二分法查找也被称为折半查找，在有序数组中查找特定元素的算法。其基本思路是：将数组分为两个部分，查找的值与中间值进行比较，如果相等则返回索引，否则通过比较确定要查找的值在数组的左半部分还是右半部分中，在新的范围内进行查找，直到找到目标值或者无法再分割为止。

二分法查找的Python实现

二分法查找的实现方式主要有两种：递归法和循环法。

递归法

递归法是通过递归函数实现。首先找到数组的中间值，然后与目标值进行比较，如果相等则返回当前索引；如果目标值小于中间值，则在左半部分进行递归调用；如果目标值大于中间值，则在右半部分进行递归调用。


def binary_search_recursion(array, target, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        return binary_search_recursion(array, target, mid + 1, end)
    else:
        return binary_search_recursion(array, target, start, mid - 1)

循环法

循环法是通过while循环实现。首先找到数组的中间值，然后与目标值进行比较，如果相等则返回当前索引；如果目标值小于中间值，则在左半部分进行下一次循环；如果目标值大于中间值，则在右半部分进行下一次循环。


def binary_search_loop(array, target):
    start = 0
    end = len(array) - 1
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return -1