Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（九）：二分查找

介紹完基本的線性表排序算法后，今天我們來介紹一種常見的線性表查找算法 —— 二分查找。

一、二分查找的引入

對于基于數(shù)字索引的數(shù)組/切片元素查找，我們可能第一反應(yīng)都是遍歷這個數(shù)組/切片，直到給定元素值和待查找的值相等時，返回索引值并退出，否則一直遍歷到最后一個元素，如果還是沒有找到則返回 -1。

這樣的查找雖然是簡單粗暴了點，但是對于規(guī)模不大的數(shù)據(jù)集，也是沒什么問題的，不過很明顯，對于 n 個元素的數(shù)組，這種查找的時間復雜度是 O(n)，隨著數(shù)據(jù)規(guī)模的增加，性能會越來越差，設(shè)想如果數(shù)據(jù)集的長度是 40 億（約為 2 的 32 次方），那么最差的情況下需要遍歷數(shù)組 40 億次，簡直不敢想象需要花費多長時間！那有沒有性能更好的算法來解決這個問題呢？

在進一步探討這個問題之前，我們先來看一個生活中的例子。我們?nèi)粘Ｉ钪校芏嗳藨?yīng)該有這種經(jīng)歷，朋友、同學或者同事淘了個寶貝，神秘兮兮的過來讓大家猜多少錢，在約定一個價格范圍之后（比如 10-100），大家會七嘴八舌的猜起價格來：

同事 A：新淘了個寶貝，猜猜多少錢？

同事 B：50塊。

同事 A：高了！

同事 C：30塊。

同事 A：低了！

同事 D：40塊。

同事 A：高了！

同事 E：36塊。

同事 A：對了！

如果我們用順序遍歷的邏輯，最差需要 91 次，才能猜到價格，現(xiàn)實生活中，沒人會這么干，我們采用上面這種邏輯，只需要 4 次就猜到價格了，快了幾十倍，而且數(shù)據(jù)量越大，優(yōu)勢越明顯。基于這種思路，我們的算法科學家提煉出了二分查找算法，幫助我們在給定數(shù)據(jù)集中快速定位要查找的元素。

二、實現(xiàn)原理

所謂二分查找，針對的是一個有序的數(shù)據(jù)集合（這點很重要），查找思想有點類似分治思想 —— 每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為 0。圖示如下：

注意：二分查找針對的必須是已經(jīng)排序過的有序數(shù)據(jù)序列，否則不能使用該算法。

三、示例代碼

二分查找的思路比較簡單，我們通過 Go 代碼實現(xiàn)如下：

package main

import (
    "fmt"
    "sort"
)

// 二分查找實現(xiàn)代碼
func binarySearch(nums []int, num int, low int, high int) int {
    // 遞歸終止條件
    if low > high {
        return -1
    }

    // 通過中間元素進行二分查找
    mid := (low + high) / 2
    // 遞歸查找
    if num > nums[mid] {
        // 如果待查找數(shù)據(jù)大于中間元素，則在右區(qū)間查找
        return binarySearch(nums, num, mid + 1, high)
    } else if num < nums[mid] {
        // 如果待查找數(shù)據(jù)小于中間元素，則在左區(qū)間查找
        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)  // 先對待排序數(shù)據(jù)序列進行排序
    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)
    }
}

對于未排序的數(shù)據(jù)序列，需要先排序，才能使用二分查找算法，這里我們使用了 Go 內(nèi)置的 sort.Ints 對整型切片進行排序，你也可以使用前面介紹的排序算法實現(xiàn)同樣的排序效果。

執(zhí)行上述代碼，打印結(jié)果如下：

四、性能分析

很顯然，二分查找的時間復雜度是 O(logn)。這是一個非常恐怖的數(shù)量級，有時候甚至比 O(1) 還要高效，比如我們要在開頭提到的 40 億個數(shù)字中查找某一個元素，也只需要32次（2 的 32 次方是 40 億數(shù)量級），這真的是非常高效了，正因如此，二分查找在線性表結(jié)構(gòu)中的應(yīng)用非常廣泛。

但是使用二分查找需要注意一個前提，那就是針對有序數(shù)據(jù)序列，換言之，二分查找適用于變動不是很頻繁的靜態(tài)序列集，如果序列集變動很頻繁，經(jīng)常進行插入刪除操作，那么就要不斷維護這個序列集的排序，這個成本也很高，因此，這種情況下就不適用二分查找了，比如我們的數(shù)據(jù)庫查詢，增刪改查很頻繁，顯然不是通過二分查找來進行查詢的。

對于這種動態(tài)數(shù)據(jù)集，要同時保證更新（包含插入和刪除）和查詢的高效，通常有兩種方案，一種是哈希表，一種是樹結(jié)構(gòu)，比如 Redis 底層就是基于哈希表的，而 MySQL 底層則是基于 B+ 樹。關(guān)于哈希表和樹結(jié)構(gòu)，我們后面會詳細介紹。