博客

二分查找算法也被称为折半查找算法，它是一种用于在有序数组中查找特定元素的算法。该算法的基本思想是将待查找区间的中间位置与待查找元素进行比较，从而将待查找区间缩小一半，直到找到目标元素或者待查找区间为空为止。

二分查找的时间复杂度为 O(log n)，比简单查找的 O(n) 更加高效。但是它要求待查找的数组必须是有序的，这也是它的局限之一。

以下是 Python 实现二分查找的代码：

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

在这个实现中，binary_search 函数接受一个有序数组 arr 和待查找的目标元素 target，返回目标元素在数组中的下标。如果目标元素不在数组中，则返回 -1。

函数首先初始化左右两个指针 left 和 right，它们分别指向数组的左右两端。接着，使用一个循环不断将待查找区间缩小一半，直到找到目标元素或者待查找区间为空为止。在循环中，首先计算待查找区间的中间位置 mid，然后将中间元素与目标元素进行比较。如果它们相等，说明已经找到目标元素，返回它的下标。如果中间元素小于目标元素，说明目标元素在右半边，缩小待查找区间的左端点。如果中间元素大于目标元素，说明目标元素在左半边，缩小待查找区间的右端点。最后，如果没有找到目标元素，返回 -1。

以下是一个调用二分查找算法的例子：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = binary_search(arr, target)
print(result)

这个例子会在数组 [1, 2, 3, 4, 5, 6, 7, 8, 9] 中查找元素 7，并打印出它在数组中的下标。由于 7 在数组中的下标为 6，所以输出结果为 6。