博客

什么是二分查找

二分查找又称折半查找，它是一种非常基础的算法，查找的前提是目标数组必须是有序的，该算法是将一个有序数组分成两半，然后判断目标元素应该在左半部分还是右半部分，然后递归对目标部分进行查找。

算法复杂度

对于长度为N的有序序列，二分查找的时间复杂度是 O(logN)，非常高效。但是要注意，二分查找算法只适用于顺序存储结构，即数组。它的实现比较简单，但是有前提条件，数据必须是有序的，而且只适用于静态查找。

二分查找的使用方法

二分查找算法的实现比较简单，但是要注意数据必须是有序的，否则得不到正确的结果。具体实现过程如下所示：

1. 定义左右指针，分别指向有序序列的起始点和终止点；
2. 取中间位置的值，并和目标值进行比较；
3. 如果中间元素大于目标元素，则目标元素只可能在左半部分，将右指针移到中间元素的左侧；
4. 如果中间元素小于目标元素，则目标元素只可能在右半部分，将左指针移到中间元素的右侧；
5. 如果中间元素等于目标元素，则找到目标元素，返回对应的下标；
6. 如果左指针大于右指针，则表示未找到目标元素，返回 -1。

以下是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:
            right = mid - 1
        else:
            left = mid + 1
    return -1

示例说明

示例一

假设我们要在以下有序数组中查找数字 5 的位置：

arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

进行二分查找，返回数字 5 在数组中的位置：

>>> binary_search(arr1, 5)
4

示例二

假设我们要在以下有序数组中查找数字 11 的位置：

arr2 = [-2, 0, 1, 3, 7, 9, 11, 15, 19, 25, 30]

进行二分查找，返回数字 11 在数组中的位置：

>>> binary_search(arr2, 11)
6

总结

二分查找是一种高效的查找算法，它的时间复杂度很低，但是只适用于顺序存储结构的有序数组。它的实现简单易懂，但是要注意数据必须是有序的，否则得不到正确的结果。