介绍完基本的线性表排序算法后，今天我们来介绍一种常见的线性表查找算法 —— 二分查找。

一、二分查找的引入

-1
nO(n)

在进一步探讨这个问题之前，我们先来看一个生活中的例子。我们日常生活中，很多人应该有这种经历，朋友、同学或者同事淘了个宝贝，神秘兮兮的过来让大家猜多少钱，在约定一个价格范围之后（比如 10-100），大家会七嘴八舌的猜起价格来：

同事 A：新淘了个宝贝，猜猜多少钱？

同事 B：50块。

同事 A：高了！

同事 C：30块。

同事 A：低了！

同事 D：40块。

同事 A：高了！

同事 E：36块。

同事 A：对了！

如果我们用顺序遍历的逻辑，最差需要 91 次，才能猜到价格，现实生活中，没人会这么干，我们采用上面这种逻辑，只需要 4 次就猜到价格了，快了几十倍，而且数据量越大，优势越明显。基于这种思路，我们的算法科学家提炼出了二分查找算法，帮助我们在给定数据集中快速定位要查找的元素。

二、实现原理

所谓二分查找，针对的是一个有序的数据集合（这点很重要），查找思想有点类似分治思想 —— 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。图示如下：

二分查找图示

注意：二分查找针对的必须是已经排序过的有序数据序列，否则不能使用该算法。

三、示例代码

二分查找的思路比较简单，我们通过 Go 代码实现如下：

package main

import (
    "fmt"
    "sort"
)

// 二分查找实现代码
func binarySearch(nums []int, num int, low int, high int) int {
    // 递归终止条件
    if low > high {
        return -1
    }

    // 通过中间元素进行二分查找
    mid := (low + high) / 2
    // 递归查找
    if num > nums[mid] {
        // 如果待查找数据大于中间元素，则在右区间查找
        return binarySearch(nums, num, mid + 1, high)
    } else if num < nums[mid] {
        // 如果待查找数据小于中间元素，则在左区间查找
        return binarySearch(nums, num, low, mid - 1)
    } else {
        // 找到了，返回索引值
        return mid
    }
}

func main() {
    nums := []int{4, 6, 5, 3, 1, 8, 2, 7}
    sort.Ints(nums)  // 先对待排序数据序列进行排序
    fmt.Printf("Sorted nums: %v\n", nums)
    num := 5
    index := binarySearch(nums, num, 0, len(nums)-1)
    if index != -1 {
        fmt.Printf("Find num %d at index %d\n", num, index)
    } else {
        fmt.Printf("Num %d not exists in nums\n", num)
    }
}
sort.Ints

执行上述代码，打印结果如下：

四、性能分析

O(logn)O(1)

但是使用二分查找需要注意一个前提，那就是针对有序数据序列，换言之，二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，因此，这种情况下就不适用二分查找了，比如我们的数据库查询，增删改查很频繁，显然不是通过二分查找来进行查询的。

对于这种动态数据集，要同时保证更新（包含插入和删除）和查询的高效，通常有两种方案，一种是哈希表，一种是树结构，比如 Redis 底层就是基于哈希表的，而 MySQL 底层则是基于 B+ 树。关于哈希表和树结构，我们后面会详细介绍。