C++二分查找

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

Question

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

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

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

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

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

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

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

     c.  當 nums[m] = target 時，說明找到 target ，因此返回索引 m 。

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

圖 10-2   二分查找流程

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

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)，當搜索區(qū)間為空時跳出（當 i > j 時為空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 計算中點索引 m
        if (nums[m] < target)    // 此情況說明 target 在區(qū)間 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情況說明 target 在區(qū)間 [i, m-1] 中
            j = m - 1;
        else // 找到目標元素，返回其索引
            return m;
    }
    // 未找到目標元素，返回 -1
    return -1;
}

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

空間復雜度 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)，當搜索區(qū)間為空時跳出（當 i = j 時為空）
    while (i < j) {
        int m = i + (j - i) / 2; // 計算中點索引 m
        if (nums[m] < target)    // 此情況說明 target 在區(qū)間 [m+1, j) 中
            i = m + 1;
        else if (nums[m] > target) // 此情況說明 target 在區(qū)間 [i, m) 中
            j = m;
        else // 找到目標元素，返回其索引
            return m;
    }
    // 未找到目標元素，返回 -1
    return -1;
}

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

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

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

優(yōu)點與局限性

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

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

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

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