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

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

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

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

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

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

分治能夠提升搜索效率，本質(zhì)上是因?yàn)楸┝λ阉髅枯喼荒芘懦粋€(gè)選項(xiàng)，而分治搜索每輪可以排除一半選項(xiàng)。

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

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

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

從原問(wèn)題 $f(0,n?1)$ 為起始點(diǎn)，通過(guò)以下步驟進(jìn)行二分查找。

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

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

圖 12-4   二分查找的分治過(guò)程

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

binary_search_recur.cpp

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

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