C++二分查找

「二分查找 binary search」是一種基于分治策略的高效搜索算法。它利用數(shù)據(jù)的有序性，每輪減少一半搜索范圍，直至找到目標(biāo)元素或搜索區(qū)間為空為止。

Question

給定一個(gè)長(zhǎng)度為 n 的數(shù)組 nums ，元素按從小到大的順序排列，數(shù)組不包含重復(fù)元素。請(qǐng)查找并返回元素 target 在該數(shù)組中的索引。若數(shù)組不包含該元素，則返回 ?1 。

圖 10-1   二分查找示例數(shù)據(jù)

如圖 10-2 所示，我們先初始化指針 $?=0$ 和 $?=??1$ ，分別指向數(shù)組首元素和尾元素，代表搜索區(qū)間 $[0,??1]$ 。請(qǐng)注意，中括號(hào)表示閉區(qū)間，其包含邊界值本身。

接下來(lái)，循環(huán)執(zhí)行以下兩步。

1. 計(jì)算中點(diǎn)索引 m=?(i+j)/2? ，其中 ?? 表示向下取整操作。
2. 判斷 nums[m] 和 target 的大小關(guān)系，分為以下三種情況。

     a.  當(dāng) nums[m] < target 時(shí)，說(shuō)明 target 在區(qū)間 [m+1,j] 中，因此執(zhí)行 i=m+1 。

     b.  當(dāng) nums[m] > target 時(shí)，說(shuō)明 target 在區(qū)間 [i,m?1] 中，因此執(zhí)行 j=m?1 。

     c.  當(dāng) nums[m] = target 時(shí)，說(shuō)明找到 target ，因此返回索引 m 。

若數(shù)組不包含目標(biāo)元素，搜索區(qū)間最終會(huì)縮小為空。此時(shí)返回 ?1 。

圖 10-2   二分查找流程

值得注意的是，由于 i 和 j 都是 int 類型，因此 i+j 可能會(huì)超出 int 類型的取值范圍。為了避免大數(shù)越界，我們通常采用公式 m=?i+(j?i)/2? 來(lái)計(jì)算中點(diǎn)。

binary_search.cpp

/* 二分查找（雙閉區(qū)間） */
int binarySearch(vector<int> &nums, int target) {
    // 初始化雙閉區(qū)間 [0, n-1] ，即 i, j 分別指向數(shù)組首元素、尾元素
    int i = 0, j = nums.size() - 1;
    // 循環(huán)，當(dāng)搜索區(qū)間為空時(shí)跳出（當(dāng) i > j 時(shí)為空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 計(jì)算中點(diǎn)索引 m
        if (nums[m] < target)    // 此情況說(shuō)明 target 在區(qū)間 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情況說(shuō)明 target 在區(qū)間 [i, m-1] 中
            j = m - 1;
        else // 找到目標(biāo)元素，返回其索引
            return m;
    }
    // 未找到目標(biāo)元素，返回 -1
    return -1;
}

時(shí)間復(fù)雜度 O(log?n) ：在二分循環(huán)中，區(qū)間每輪縮小一半，循環(huán)次數(shù)為 log2?n 。

空間復(fù)雜度 O(1) ：指針 i 和 j 使用常數(shù)大小空間。

binary_search.cpp

/* 二分查找（左閉右開） */
int binarySearchLCRO(vector<int> &nums, int target) {
    // 初始化左閉右開 [0, n) ，即 i, j 分別指向數(shù)組首元素、尾元素+1
    int i = 0, j = nums.size();
    // 循環(huán)，當(dāng)搜索區(qū)間為空時(shí)跳出（當(dāng) i = j 時(shí)為空）
    while (i < j) {
        int m = i + (j - i) / 2; // 計(jì)算中點(diǎn)索引 m
        if (nums[m] < target)    // 此情況說(shuō)明 target 在區(qū)間 [m+1, j) 中
            i = m + 1;
        else if (nums[m] > target) // 此情況說(shuō)明 target 在區(qū)間 [i, m) 中
            j = m;
        else // 找到目標(biāo)元素，返回其索引
            return m;
    }
    // 未找到目標(biāo)元素，返回 -1
    return -1;
}

如圖 10-3 所示，在兩種區(qū)間表示下，二分查找算法的初始化、循環(huán)條件和縮小區(qū)間操作皆有所不同。

由于“雙閉區(qū)間”表示中的左右邊界都被定義為閉區(qū)間，因此指針 i 和 j 縮小區(qū)間操作也是對(duì)稱的。這樣更不容易出錯(cuò)，因此一般建議采用“雙閉區(qū)間”的寫法。

圖 10-3   兩種區(qū)間定義

優(yōu)點(diǎn)與局限性

二分查找在時(shí)間和空間方面都有較好的性能。

• 二分查找的時(shí)間效率高。在大數(shù)據(jù)量下，對(duì)數(shù)階的時(shí)間復(fù)雜度具有顯著優(yōu)勢(shì)。例如，當(dāng)數(shù)據(jù)大小 n=2^20 時(shí)，線性查找需要 2^20=1048576 輪循環(huán)，而二分查找僅需 log2 ?2^20=20 輪循環(huán)。
• 二分查找無(wú)須額外空間。相較于需要借助額外空間的搜索算法（例如哈希查找），二分查找更加節(jié)省空間。

然而，二分查找并非適用于所有情況，主要有以下原因。

• 二分查找僅適用于有序數(shù)據(jù)。若輸入數(shù)據(jù)無(wú)序，為了使用二分查找而專門進(jìn)行排序，得不償失。因?yàn)榕判蛩惴ǖ臅r(shí)間復(fù)雜度通常為 O(nlog?n) ，比線性查找和二分查找都更高。對(duì)于頻繁插入元素的場(chǎng)景，為保持?jǐn)?shù)組有序性，需要將元素插入到特定位置，時(shí)間復(fù)雜度為 O(n) ，也是非常昂貴的。
• 二分查找僅適用于數(shù)組。二分查找需要跳躍式（非連續(xù)地）訪問(wèn)元素，而在鏈表中執(zhí)行跳躍式訪問(wèn)的效率較低，因此不適合應(yīng)用在鏈表或基于鏈表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。
• 小數(shù)據(jù)量下，線性查找性能更佳。在線性查找中，每輪只需要 1 次判斷操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判斷操作、1 次加法（減法），共 4 ~ 6 個(gè)單元操作；因此，當(dāng)數(shù)據(jù)量 n 較小時(shí)，線性查找反而比二分查找更快。