我們已經(jīng)學過，搜索算法分為兩大類。

• 暴力搜索：它通過遍歷數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，時間復雜度為 $O(n)$ 。
• 自適應搜索：它利用特有的數(shù)據(jù)組織形式或先驗信息，可達到 $O(\log ?n)$ 甚至 $O(1)$ 的時間復雜度。

實際上，時間復雜度為 $O(\log ?n)$ 的搜索算法通常都是基于分治策略實現(xiàn)的，例如二分查找和樹。

• 二分查找的每一步都將問題（在數(shù)組中搜索目標元素）分解為一個小問題（在數(shù)組的一半中搜索目標元素），這個過程一直持續(xù)到數(shù)組為空或找到目標元素為止。
• 樹是分治關系的代表，在二叉搜索樹、AVL 樹、堆等數(shù)據(jù)結(jié)構(gòu)中，各種操作的時間復雜度皆為 $O(\log ?n)$ 。

二分查找的分治策略如下所示。

• 問題可以被分解：二分查找遞歸地將原問題（在數(shù)組中進行查找）分解為子問題（在數(shù)組的一半中進行查找），這是通過比較中間元素和目標元素來實現(xiàn)的。
• 子問題是獨立的：在二分查找中，每輪只處理一個子問題，它不受另外子問題的影響。
• 子問題的解無須合并：二分查找旨在查找一個特定元素，因此不需要將子問題的解進行合并。當子問題得到解決時，原問題也會同時得到解決。

分治能夠提升搜索效率，本質(zhì)上是因為暴力搜索每輪只能排除一個選項，而分治搜索每輪可以排除一半選項。

基于分治實現(xiàn)二分

在之前的章節(jié)中，二分查找是基于遞推（迭代）實現(xiàn)的?，F(xiàn)在我們基于分治（遞歸）來實現(xiàn)它。

從分治角度，我們將搜索區(qū)間 $[i,j]$ 對應的子問題記為 $f(i,j)$ 。

從原問題 $f(0,n?1)$ 為起始點，通過以下步驟進行二分查找。

1. 計算搜索區(qū)間 $[i,j]$ 的中點 $m$ ，根據(jù)它排除一半搜索區(qū)間。
2. 遞歸求解規(guī)模減小一半的子問題，可能為 $f(i,m?1)$ 或 $f(m+1,j)$ 。
3. 循環(huán)第 1. 和 2. 步，直至找到 target 或區(qū)間為空時返回。

圖 12-4 展示了在數(shù)組中二分查找元素 $6$ 的分治過程。

圖 12-4   二分查找的分治過程

在實現(xiàn)代碼中，我們聲明一個遞歸函數(shù) dfs() 來求解問題 $f(i,j)$ 。

binary_search_recur.cpp

/* 二分查找：問題 f(i, j) */
int dfs(vector<int> &nums, int target, int i, int j) {
    // 若區(qū)間為空，代表無目標元素，則返回 -1
    if (i > j) {
        return -1;
    }
    // 計算中點索引 m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 遞歸子問題 f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 遞歸子問題 f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // 找到目標元素，返回其索引
        return m;
    }
}

/* 二分查找 */
int binarySearch(vector<int> &nums, int target) {
    int n = nums.size();
    // 求解問題 f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}