二分搜尋

二分查找（binary search）是用於查找有序數組中目標值位置的搜索算法。二分查找比較目標值與陣列中間元素的大小，如果兩者不相等，則會捨棄不可能包含目標值的那一半區間，然後在剩餘區間重複此過程：每次選取新的中間元素並與目標值比較，直至找到目標或區間為空。若區間為空，則說明目標值不存在。

二分查找在最好、最壞、平均情況下的時間複雜度為對數級別，即需做$O(\log n)$次比較，其中$n$是陣列元素的數量。符號$O$是漸近符號，$\log$表示對數。在此標記下，對數的底數通常無關緊要，因為不同底數的對數之間只相差一個常數因子。具體來說，有$\log_b(n) = \log_k(n) \div \log_k(b)$，而$\log_k(b)$是常數。除規模較小的陣列外，二分查找通常比線性搜索更快。二分查找的搜索效率可能不及哈希表等數據結構，但其還可用於查找最接近目標值的上界或下界，即使目標值不在陣列中。

二分查找有許多其他形式。例如，分數級聯能加快在多個陣列中查找同一數值的速度，還能高效地解決計算幾何等領域的搜索問題；指數搜索則將搜索範圍擴展至無界列表。二叉搜索樹和B樹等數據結構的實現也基於二分查找原理。

## 演算法

二分查找適用於有序數組。其首先比較陣列中間的元素與目標值：如果目標值與該元素匹配，則返回其在陣列中的位置；如果目標值小於該元素，則在陣列較小的那一半中繼續查找；如果目標值大於該元素，則在陣列較大的那一半中繼續查找。通過這種方法，每次迭代都能將搜索範圍縮小一半。

### 過程

給定包含$n$個元素的陣列$A$，其中的值或記錄分別為$A_0,A_1,A_2,\ldots,A_{n-1}$，且滿足$A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}$。假設目標值為$T$。下面的子程序使用二分查找來尋找$T$在陣列$A$中的索引。

- 令$L$為$0$，$R$為$n-1$。
- 如果$L>R$，則搜索失敗並終止。
- 令$m$（中間元素的位置）為$\frac{L+R}{2}$的向下取整值，即不大於$\frac{L+R}{2}$的最大整數。
- 如果$A_m < T$，則令$L$為$m+1$，回到步驟2。
- 如果$A_m > T$，則令$R$為$m-1$，回到步驟2。
- 如果$A_m = T$，則搜索完成，返回$m$。

該過程使用兩個變量$L$和$R$來跟蹤搜索邊界。該過程可以用偽代碼表示如下，其中變量名和類型與上文相同，`floor`為下取整函數，`unsuccessful`表示搜索失敗時的特定返回值：

```
'''function''' binary_search(A, n, T) '''is'''
    L := 0
    R := n &minus; 1
    '''while''' L ≤ R '''do'''
        m := floor((L + R) / 2)
        '''if''' A[m] < T '''then'''
            L := m + 1
        '''else if''' A[m] > T '''then'''
            R := m &minus; 1
        '''else''':
            '''return''' m
    '''return''' unsuccessful
```

也可令$m$為$\frac{L+R}{2}$的向上取整值。如此所做，若目標值在陣列中出現多次，則結果可能會有所不同。

#### 另一過程

上述過程中，每次迭代都會檢查中間元素$m$是否等於目標值$T$。而在其他一些實現中，此檢查僅在最後剩餘一個元素（即$L=R$）時執行，而每次迭代時不再執行比較。和前述過程相比，此方式平均多一輪迭代，但每輪迭代時少做一次比較。

赫爾曼·博滕布魯赫於1962年首次發表了省略此檢查的實現。

- 令$L$為$0$，$R$為$n-1$。
- 當$L \neq R$時。
- 令$m$（中間元素的位置）為$\frac{L+R}{2}$的向上取整值，即不小於$\frac{L+R}{2}$的最小整數。
- 如果$A_m > T$，令$R$為$m-1$。
- 否則說明$A_m \leq T$，令$L$為$m$。
- 現在$L=R$，搜索完成。如果$A_L=T$，返回$L$。否則，搜索失敗並終止。

該版本的偽代碼如下，其中`ceil`是上取整函數：

```
'''function''' binary_search_alternative(A, n, T) '''is'''
    L := 0
    R := n &minus; 1
    '''while''' L != R '''do'''
        m := ceil((L + R) / 2)
        '''if''' A[m] > T '''then'''
            R := m &minus; 1
        '''else''':
            L := m
    '''if''' A[L] = T '''then'''
        '''return''' L
    '''return''' unsuccessful
```

### 重複元素

若陣列中有重複元素，算法會返回任一符合目標值的索引。例如，如果要搜索的陣列為$[1,2,3,4,4,4,4,5,6,7]$，且目標值為$4$，那麼演算法返回第4個至第7個元素（索引為3至6）都是正確的。然而，有時需要找到目標值在陣列中重複出現的最左側或最右側的元素。在上述例子中，第4個元素是值為4的最左側元素，而第7個元素是值為4的最右側元素。若對應元素存在，上述的另一過程總是會返回最右側元素的索引。

#### 查找最左側元素的過程

要查找最左邊的元素，可以使用以下過程：

- 令$L$為$0$，$R$為$n$。
- 當$L < R$時。
- 令$m$（中間元素的位置）為$\frac{L+R}{2}$的向下取整值，即不大於$\frac{L+R}{2}$的最大整數。
- 如果$A_m < T$，令$L$為$m+1$。
- 否則說明$A_m \geq T$，令$R$為$m$。
- 返回$L$。

如果$L < n$且$A_L = T$，那麼$A_L$是等於$T$的最左側元素。即使$T$不在陣列中，$L$也是$T$在陣列中的排名，即陣列中小於$T$的元素數量。

該版本的偽代碼如下，其中`floor`是下取整函數：

```
'''function''' binary_search_leftmost(A, n, T) '''is'''
    L := 0
    R := n
    '''while''' L < R '''do'''
        m := floor((L + R) / 2)
        '''if''' A[m] < T '''then'''
            L := m + 1
        '''else''':
            R := m
    '''return''' L
```

#### 查找最右側元素的過程

要查找最右邊的元素，可以使用以下過程：

- 令$L$為$0$，$R$為$n$。
- 當$L < R$時。
- 令$m$（中間元素的位置）為$\frac{L+R}{2}$的向下取整值，即不大於$\frac{L+R}{2}$的最大整數。
- 如果$A_m > T$，令$R$為$m$。
- 否則說明$A_m \leq T$，令$L$為$m+1$。
- 返回$R - 1$。

如果$R > 0$ 且$A_{R-1}=T$，那麼$A_{R-1}$是等於$T$的最右側元素。即使$T$不在陣列中，$n-R$也是陣列中大於$T$的元素數量。

該版本的偽代碼如下，其中`floor`是下取整函數：

```
'''function''' binary_search_rightmost(A, n, T) '''is'''
    L := 0
    R := n
    '''while''' L < R '''do'''
        m := floor((L + R) / 2)
        '''if''' A[m] > T '''then'''
            R := m
        '''else''':
            L := m + 1
    '''return''' R - 1
```

### 近似匹配

二分查找可用於近似匹配。上圖中，目標值$5$本身不在陣列中，但通過近似匹配，能計算出其排名、前驅、後繼、最近鄰

二分查找不僅能精確定位目標值，也可方便地擴展到近似匹配，例如可以用來計算給定值的排名（即比它小的元素的數量）、前驅（前一個較小的元素）、後繼（下一個較大的元素）、最近鄰。而範圍查找 (電腦科學)（查找兩個值之間的元素數量）可利用查詢兩次排名得到。

- 查詢排名可以使用查找最左側元素的過程來完成。程序的返回值即為小於目標值的元素數量。
- 查詢前驅可以通過查詢排名來執行。如果目標值的排名為$r$，那麼其前驅的位置為$r-1$。
- 對於後繼查詢，可以查找最右側元素。如果得到的結果為$r$，那麼目標值的後繼位置就是$r+1$。
- 目標值的最近鄰是其前驅或後繼之一，取決於哪個值更接近。
- 範圍查找也很簡單。一旦知道了兩個值的位置，區間內大於等於第一個值且小於第二個值的元素數量就是兩個位置之差。考慮到是否需要將區間的端點包含在內，以及陣列中是否包含與端點匹配的元素，左右端點的排名值可能會有調整。

## 性能

此章節中，$\lfloor\cdot \rfloor$表示向下取整，$\log_2$是以2為底的對數。

二分查找的過程可以構建成一棵二叉樹，從而得到其比較次數並分析性能。樹的根節點是陣列的中間元素，左半部分的中間元素是根節點的左子節點，右半部分的中間元素是根節點的右子節點，其餘部分以類似方式構建。搜索過程從根節點開始，根據目標值是小於還是大於當前節點的值來選擇遍歷左子樹還是右子樹。

最壞情況下，二分查找需要比較$\lfloor \log_2 (n) + 1 \rfloor$次，此時搜索會達到樹的最深層。對於任何二分查找過程，樹的層數總為$\lfloor \log_2 (n) + 1 \rfloor$。若目標元素不在陣列中，可能會發生最壞情況：若$n$可以表示為2的某次冪減1，那麼查找過程總會遍歷到最深層，一定會發生最壞情況；否則，搜索過程可能會在倒數第二層中止，此時比較了$\lfloor \log_2 (n) \rfloor$次，比最壞情況少一次。

平均情況下，當目標元素在陣列中時，二分查找的比較次數是$\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n$（假設每個元素被搜索的機率相等），近似於$\log_2(n) - 1$；若目標元素不在陣列中，二分查找的比較次數平均為$\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)$（假設範圍內及範圍外的元素被搜索的機率相等）。

最好情況下，即目標值正好是陣列的中間元素，二分查找在一次比較後就能返回其位置。

從迭代次數的角度看，沒有任何一種僅通過比較元素大小進行搜索的演算法，在平均情況和最壞情況下的性能優於二分查找。表示二分查找的比較樹除最底層外，每一層都是完全填滿的，因此層數最少。任何僅通過元素比較進行搜索的演算法，都可以用一棵二叉比較樹來表示。這棵樹中，從根節點出發，到達任意已存在節點的路徑稱為「內部路徑」（internal path）。定義$I$為所有內部路徑的長度總和，即「內部路徑長度」（internal path length）。如果陣列中的每個元素被搜索到的機率相等，那麼搜索算法的平均迭代次數為$1 + \frac{I}{n}$。換言之，該值即為樹中所有內部路徑長度的平均值再加上根節點處的第一次迭代。之所以如此，是因為內部路徑表示搜索算法在尋找目標元素時比較過的元素，而這些路徑長度則表示從根節點之後的迭代次數。因此，將這些路徑長度的平均值加上根節點處的一次迭代，即得到了平均情況的迭代次數。為讓平均比較次數最少，必須使內部路徑長度$I$最小。事實上，二分查找構成的樹即滿足最小內部路徑長度的條件。Knuth（1998）證明，若樹中所有外部節點（即沒有子節點的節點）均位於連續的兩層內，則該樹的外部路徑長度（外部路徑即指所有從根節點到外部節點的路徑）最小。這一結論同樣適用於內部路徑，因為內部路徑長度$I$與外部路徑長度$E$存在線性關係$I = E - 2n$（$n$為樹的節點數）。當每個子樹的節點數量近似相同時（也就是每次迭代時都將陣列大致分為兩半），樹中所有外部節點及其直接父節點都將位於連續兩層內。因此，二分查找對應的二叉比較樹具有最小的內部路徑長度，從而使得二分查找的平均比較次數達到最小。如果不以此方式構造樹，搜索算法在每次迭代中只能排除較少的元素，從而增加平均情況及最壞情況下所需的迭代次數。其他基於元素比較的搜索算法便屬於這種情況：雖然它們查詢某些目標值時可能更快，但若綜合考慮所有元素，其平均性能均不及二分查找。二分查找每次將陣列一分為二，保證兩個子陣列的大小儘可能相近。

### 空間複雜度

二分查找需要使用三個指針（可能為陣列索引，或指向記憶體地址的指針），與陣列本身大小無關。因此，在word RAM計算模型中，二分查找的空間複雜度為$O(1)$。

### 平均情況的推導

二分查找的平均迭代次數取決於每個元素被搜索到的機率，而成功搜索與失敗搜索的平均情況不同。對於成功搜索，則需假設每個元素被搜索的機率相等；對於失敗搜索，則需假設陣列元素之間及元素之外的每個區間被搜索的機率相等。成功搜索的平均情況是搜索陣列中每個元素所需迭代次數之和除以元素數量$n$，失敗搜索的平均情況則是搜索陣列各區間所需迭代次數之和除以區間數量$n + 1$。

#### 成功搜索

在二叉樹的表示法中，一次成功搜索可以表示為從樹的根節點到目標節點的路徑，稱為「內部路徑」（internal path）。路徑長度等於路徑中經過的邊（節點之間的連接）數目。如果一條路徑長度為$l$，則對應搜索所需的迭代次數為$l + 1$（包括初始迭代）。所有內部路徑長度之和稱作「內部路徑長度」（internal path length）。由於從根節點到任何特定節點僅存在一條路徑，因此每條內部路徑表示對特定元素的一次搜索。如果有$n$個元素（$n$為正整數），內部路徑長度記為$I(n)$，則成功搜索的平均迭代次數$T(n) = 1 + \frac{I(n)}{n}$（其中$1$表示初始迭代）。

由於二分查找是基於元素比較的最優搜索算法，因此問題可簡化為求解含$n$個節點的所有可能二叉樹中的最小內部路徑長度，表達式如下：

$$I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor$$

例如，對於含7個元素的陣列，根節點對應的搜索需1次迭代，下一層的兩個節點各需2次，再下一層的四個節點各需3次。因此。

$$\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10$$

根據成功搜索平均情況的公式，此時的平均迭代次數為$1 + \frac{10}{7} = 2 \frac{3}{7}$。

上述內部路徑長度$I(n)$的求和公式可進一步化簡為：

$$I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2$$

將此式代入成功搜索平均迭代次數$T(n)$的表達式中，得到：

$$T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n$$

當$n$為整數時，其與前述成功搜索的平均情況公式完全相同。

#### 失敗搜索

失敗搜索可在樹中增加額外節點以表示，這種結構稱為擴展二叉樹（extended binary tree）。當樹中已有節點（即內部節點）不足兩個子節點時，需為之添加額外的子節點（即外部節點），使每個內部節點都有兩個子節點。這樣一來，失敗搜索的過程便可表示為從根節點到外部節點的一條路徑，這個外部節點的父節點即為搜索結束時剩下的唯一元素。從根節點到外部節點的路徑稱為「外部路徑」（external path）。所有外部路徑的長度之和稱作「外部路徑長度」（external path length）。若元素個數為正整數$n$，外部路徑長度為$E(n)$，則失敗搜索的平均迭代次數$T'(n)=\frac{E(n)}{n+1}$（其中$1$表示初始迭代）。公式中除以$n+1$而非$n$的原因是，樹中有$n+1$條外部路徑，它們分別表示陣列元素之間以及陣列邊界之外的各個區間。

同樣地，這一問題可以簡化為確定含$n$個節點的所有二叉樹中的最小外部路徑長度。對於任意二叉樹，外部路徑長度與內部路徑長度之間滿足$E(n) = I(n) + 2n$。將先前得到的$I(n)$表達式代入，則有：

$$E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}$$

再將上式代入平均迭代次數$T'(n)$的公式，便可求出失敗搜索的平均迭代次數：

$$T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{n+1} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)$$

#### 另一過程的性能

前文定義的二分查找過程，每次迭代需要做一次或兩次比較，其中每次迭代都會檢查中間元素是否與目標相等。假設每個元素被搜索到的機率均等，那麼平均每次迭代的比較次數為1.5次。還有一種實現方法是待搜索結束後，再檢查中間元素是否與目標值相等。平均而言，這種方法每次迭代可減少0.5次比較，略微降低了大部分電腦上每次迭代的運行時間。然而，這種方式一定會達到最多的迭代次數，搜索過程平均會額外增加一次迭代。因為即使在最壞情況下，二分查找的比較循環也只執行$\lfloor \log_2 (n) + 1 \rfloor$次，因此除非$n$極大，否則每次迭代效率的微小提升不足以彌補額外增加的迭代次數。Knuth（1998）使用其設計的MIX (電腦模型)發現，對於成功搜索而言，前述演算法（即二分查找在每次迭代末尾檢查元素相等性）的平均運行時間為$17.5 \log_2 n + 17$個單位，而標準二分查找的平均運行時間則為$18 \log_2 n - 16$個單位。前者的時間複雜度增長稍慢，但初始複雜度更高。

### 運行時間和緩存使用

在分析二分查找的性能時，還需考慮比較兩個元素的所需的時間。整數和字串的比較時間通常與其編碼長度（一般以位數表示）呈線性關係。假設逐位比較，與32位無符號整數相比，64位無符號整數的比較時間至多是前者最壞情況（即兩個整數相同）的兩倍。如果元素的編碼長度較大（例如大整數類型或長字串），比較操作的開銷會顯著增加。此外，比較浮點數（實數在電腦中最常用的表示方式）通常也比整數和短字串耗時更多。

多數電腦架構中，CPU內部配有獨立於記憶體（RAM）的硬體緩存，容量極小但速度極快。因此，考慮到訪問局部性，多數CPU會存儲最近訪問的記憶體地址及其附近地址的數據。就陣列而言，CPU訪問某個元素時，會同時緩存該元素以及在RAM中與之相鄰的元素，從而更快地順序訪問索引相近的陣列元素。然而，二分查找每次跳躍到陣列中點，記憶體跨度往往較大，不像線性搜索或哈希表的線性探測那樣具有良好局部性。因此查找較大陣列時，實際耗時可能略高於理論預期。

## 與其他方案的比較

在有序數組中，當插入和刪除操作與查找操作交替進行時，每次插入或刪除操作的時間複雜度為$O(n)$，效率低下。此外，有序數組的記憶體使用情況可能較為複雜，特別是在需要頻繁插入元素的情況下。其他一些數據結構能更高效地支持插入與刪除操作。二分查找可以用於精確匹配和集合 (抽象數據類型)（即判斷目標值是否存在於某個集合內）。雖然一些數據結構能夠更快地精確匹配與檢測集合成員，但二分查找還可用於高效地執行近似匹配，通常不論值的類型或結構如何，其近似匹配的性能都能達到$O(\log n)$。此外，有序數組上還能高效完成一些操作，例如獲取最小值和最大值。

### 線性搜索

線性搜索是簡單的搜索算法，其逐個檢查記錄，直到找到目標值為止。線性搜索可在鍊表上實現，其插入和刪除操作比陣列更快。對於有序數組，除非陣列很短，否則二分查找通常比線性搜索更快。不過二分查找需要提前對數組排序，Knuth（1998）對這兩種搜索算法的運行時間做了形式化分析。在Knuth設計的MIX (電腦模型)上，對於成功搜索，二分查找平均耗時為$18 \log n - 16$個單位；而在陣列末尾加入哨兵節點的線性搜索平均耗時為$1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}$個單位。線性搜索的計算量很少，故初始複雜度較低，但隨規模增長，其複雜度很快便會超過二分查找。在MIX電腦上，只有當$n > 44$時，二分查找的性能才會超過帶哨兵的線性搜索。所有基於元素比較的排序算法（例如快速排序和歸併排序），最壞情況下都至少需要做$O(n \log n)$次比較。與線性搜索不同，二分查找還能高效地進行近似匹配。此外，在有序數組中，查找最大或最小元素等操作可以高效完成，而無序數組則無法做到。

### 二叉樹

二叉搜索樹是基於二分查找原理構建的二叉樹數據結構。樹中元素按序排列，每個元素都可使用類似二分查找的方法執行搜索，其平均時間複雜度為對數級別。二叉搜索樹的插入和刪除操作平均也為對數時間，通常比有序數組插入和刪除的線性時間更快。同時，二叉樹也保留了有序數組的所有操作能力，包括範圍查詢和近似查詢。

不過，二分查找在搜索操作上通常更高效，因為二叉搜索樹往往不是完美平衡的，性能會稍遜於二分查找。即使是平衡樹（能夠自我平衡的二叉搜索樹），也很少能達到理論上層數最少的狀態。非平衡二叉樹甚至可能嚴重失衡，內部節點（具有兩個子節點的節點）數量很少，此時的平均和最壞搜索性能可能接近$n$次比較。此外，二叉搜索樹占用的空間也比有序數組更大。

二叉搜索樹在外部存儲設備（如硬碟）的搜索中具有優勢，因為可以在文件系統中有效組織。B樹推廣了這一樹結構的組織方式，常用於資料庫和文件系統等長期存儲系統。

### 哈希表

哈希表是將鍵映射到對應記錄的數據結構，一般使用哈希函數實現。對於關聯數組，哈希表通常比有序數組上的二分查找更快。大部分哈希表的實現，其平均時間複雜度僅為平攤的常數時間。但哈希表只在搜索失敗時告知目標不存在，而不能給出鄰近值的資訊，因此不適合近似匹配，若執行查找下一個較小值、下一個較大值或者最近的鍵值等操作，效果不佳。二分查找則非常適合近似匹配，且能在對數時間內完成。此外，諸如查找最大或最小元素等操作，在有序數組上可高效完成，而哈希表無法輕易做到。

### 集合

集合 (抽象數據類型)是與搜索類似的問題，任何像二分查找這樣的搜索算法都可用於集合成員檢測。但也有一些專門用於集合成員檢測的演算法。例如，當鍵值範圍有限時，位數組是最簡單的選擇。該結構緊湊地存儲一系列位，每位代表一個特定範圍內的鍵值。位數組的速度非常快，查詢僅需$O(1)$時間。朱迪矩陣中的Judy1類型則能有效處理64位鍵值。

對於近似結果，布隆過濾器是基於哈希函數的機率型數據結構，其使用位數組和多個哈希函數對鍵編碼，以存儲鍵集合。多數情況下，布隆過濾器比位數組的空間利用率更高，且速度也不會明顯變慢：若使用$k$個哈希函數，成員查詢僅需$O(k)$時間。不過，布隆過濾器存在誤報問題。

### 其他數據結構

某些情況下，一些數據結構可能在搜索操作和其他適用於有序數組的操作上比二分查找更高效。對於搜索、近似匹配及有序數組上的一些操作，可以使用專門的數據結構，如van Emde Boas樹、融合樹、字典樹（trie）、位數組。這些數據結構通常只有在特定屬性的鍵值（如小整數鍵值）上更快，否則可能會導致時間或空間效率降低。只要鍵值能被排序，這些操作在有序數組上仍能保持較高的效率。某些數據結構（如朱迪矩陣）結合了多種方法，不僅緩解了這些問題，還能保持較高效率，同時能夠近似匹配。

## 其他形式

### 統一二分查找

統一二分查找存儲的不是上下界，而是從當前中間元素到下一次迭代的中間元素間的索引差值，會將之事先存入查找表中。例如，要搜索的陣列若為1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11，當前的中間元素$m$是6。此時，左側子陣列1, 2, 3, 4, 5的中間元素是3，右側子陣列7, 8, 9, 10, 11的中間元素是9。統一二分查找會存儲3這個差值（因為從6到左右兩個中間元素的索引距離都是3）。為了縮小搜索空間，演算法每次將這個差值與當前中間索引相加減。在某些不便於計算中點的系統（如十進位計算機）中，這種方法可能更快。

### 指數搜索

指數搜索將二分查找擴展到無界列表。它先會查找首個索引為2的冪且元素大於目標值的位置，然後將該位置作為上界，再切換至二分查找。若目標值的位置為$x$，則在開始二分查找之前，指數搜索最多需要進行$\lfloor \log_2 x + 1\rfloor$次迭代，此後最多再進行$\lfloor \log_2 x \rfloor$次二分查找的迭代。指數搜索也適用於有界列表，但僅當目標值位於陣列的開頭附近時，才比直接使用二分查找更高效。

### 插值搜索

插值搜索不是每次計算中點，而是估算目標元素的位置。估算會考慮陣列的最小值、最大值以及陣列長度。其基本思路是：中點在很多情況下並非最理想的猜測位置。例如，如果目標值接近陣列中的最大值，那麼目標值很可能靠近陣列末尾。

插值函數中最常見的是線性插值。設陣列為$A$，下界為$L$，上界為$R$，目標值為$T$，則目標位置的估計值為$(T - A_L) / (A_R - A_L)$。若使用線性插值，且陣列元素分布均勻或接近均勻，則插值搜索的比較次數為$O(\log \log n)$。

對於較小的陣列，插值搜索由於有額外的計算開銷，其速度通常會比二分查找慢。儘管插值搜索的時間複雜度增長更慢，但只有在陣列規模較大時，這種優勢才能抵消額外計算所需的開銷。

### 分數級聯

分數級聯是用於在多個有序數組中快速搜索同一元素的技術。如果逐個搜索每個陣列，時間複雜度為$O(k \log n)$，其中$k$為陣列個數。分數級聯在每個陣列中存儲關於元素在其他陣列位置的資訊，將時間複雜度降至$O(k + \log n)$。

分數級聯最初是為了解決計算幾何中的多種搜索問題而開發的。後來，它也被應用於數據挖掘和網際網路協議（IP）路由中。

### 圖的推廣形式

二分查找還被推廣到某些類型的圖結構，其中目標值存儲於圖的頂點中，而非陣列元素內。二叉搜索樹即是這種推廣的特例。當在樹中查詢某個節點時，演算法要麼確定這個節點就是目標，要麼知道目標元素所在的子樹位置。但推廣形式還可以更進一步：給定無向正權圖及目標頂點，每次查詢一個頂點時，演算法要麼知道這個頂點就是目標，要麼獲得從該頂點到目標頂點的最短路徑上的某條邊資訊。實際上，標準二分查找是圖為路徑時的特例，而二叉搜索樹則對應於當查詢的頂點不為目標時給出左或右子樹邊的情況。對於所有無向正權圖，均存在演算法，最壞情況下也能通過$O(\log n)$次查詢，找到目標頂點。

### 噪聲二分查找

噪聲二分查找用於處理演算法無法可靠地比較陣列元素的情況，即比較每對元素大小時，都有一定機率出錯。噪聲二分查找可在給定的機率下確定目標元素正確的位置，這一機率控制著結果的可靠性。任何噪聲二分查找過程期望比較次數至少為$(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}$，其中$H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)$ 為二元熵函數，$\tau$表示最終輸出錯誤位置的機率。噪聲二分查找問題也可視作Rényi-Ulam game的特例，即基於20個問題的一種版本，其中回答可能會出錯。

### 量子二分查找

經典電腦執行二分查找時，在最壞情況下的迭代次數嚴格為$\lfloor \log_2 n + 1 \rfloor$。量子演算法執行二分查找的查詢次數（對應經典演算法的迭代次數）仍然與$\log_2 n$成正比，但常數因子小於1，因此在量子計算機上具有更低的時間複雜度。任何精確（即總能返回正確結果）的量子二分查找演算法，最壞情況下至少需要$\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n$次查詢（其中$\ln$為自然對數）。目前已經發現一種精確的量子二分查找演算法，在最壞情況下的查詢次數為$4 \log_{605} n \approx 0.433 \log_2 n$。相比之下，格羅弗算法是用於搜索無序列表的最優量子演算法，所需的查詢次數為$O(\sqrt{n})$。

## 歷史

排序列表元素以提高查找效率，這一思想古已有之。目前已知最早的實例是約公元前200年巴比倫的「Inakibit-Anu」泥板，其包含約500個六十進位的數字及其倒數，數字按字典序排列，以便更快地找到特定的元素。此外，愛琴海諸島上也發現了一些按照姓名首字母排序的人名列表。1286年完成的拉丁語詞典《Catholicon》，首次給出了完整的字母排序規則，而不僅僅是依照單詞前幾個字母排序。

1946年，約翰·莫奇利在摩爾學院講座（一門電腦科學領域的奠基性課程）中首次提及了二分查找。1957年，威廉·韋斯利·彼得森發表了首個插值搜索算法。早期的二分查找算法均只能用於長度為2的冪次減一的陣列。直至1960年，德里克·亨利·萊默提出適用於任意長度數組的二分查找演算法。1962年，赫爾曼·博滕布魯赫在ALGOL 60語言中實現了另一種二分查找版本，將判斷相等的比較操作放在末尾，雖使平均迭代次數增加了一次，但每次迭代所需的比較次數減少至一次。統一二分查找則由史丹福大學的A.K.錢德拉（A. K. Chandra）於1971年開發。1986年，貝爾納·沙澤勒與利奧尼達斯·J·吉巴斯引入了「分數級聯」概念，用以解決計算幾何中的諸多查找問題。

## 實現問題

儘管二分查找的基本思想相對簡單，但其細節卻出奇複雜。

喬恩·本特利在為職業程式設計師開設的一門課程中布置了二分查找的練習，發現90%的學生在數小時後仍未給出正確解答，主要問題是演算法實現有誤而無法運行，或是在極少數邊緣案例下返回錯誤答案。1988年發表的一項研究顯示，二十本教材中只有五本給出了準確的二分查找代碼。此外，本特利自身在1986年出版的《編程珠璣》一書中給出的二分查找實現存在溢出錯誤，這個錯誤二十餘年未被發現。Java程式語言庫中的二分查找實現也存在相同的溢出問題，且該問題持續了九年多。

在實際編程中，表示索引的變量通常是固定大小的整數。因此在處理非常大的陣列時，可能會導致算術溢出。如果使用$\frac{L+R}{2}$計算中點，即使$L$和$R$的值都在所用數據類型的表示範圍內，$L+R$的值仍可能會超過範圍。如果$L$和$R$都是非負數，可以通過計算$L+\frac{R-L}{2}$來避免這種情況。

如果循環的退出條件定義不正確，可能會導致無限循環。當$L$超過$R$時，表示搜索失敗，必須返回失敗的資訊。另外，循環應在找到目標元素時退出；若不這麼做，那麼在循環結束後，必須檢查是否成功找到目標元素。本特利發現，大多數在實現二分查找時出錯的程式設計師，都是退出條件出了錯。

## 庫支持

許多程式語言的標準庫包含二分查找例程：

- C語言在其標準庫中提供了`bsearch()`函數，通常使用二分查找實現，儘管官方標準中並未強制要求。
- C++的標準庫中提供了`binary_search()`、`lower_bound()`、`upper_bound()`、`equal_range()`函數。
- D語言的標準庫Phobos在`std.range`模塊中提供了`SortedRange`類型（由`sort()`和`assumeSorted()`函數返回），該類型包含`contains()`、`equaleRange()`、`lowerBound()`、`trisect()`方法，這些方法默認對提供隨機訪問的範圍使用二分查找技術。
- COBOL提供了`SEARCH ALL`動詞，用於對COBOL有序表執行二分查找。
- Go的`sort`標準庫包包含`Search`、`SearchInts`、`SearchFloat64s`、`SearchStrings`函數，分別實現了通用的二分查找，以及針對整數、浮點數、字串切片的特定實現。
- Java在標準`java.util`包的java/util和java/util類中提供了一組重載的`binarySearch()`靜態方法，用於對Java陣列和`List`（列表）執行二分查找。
- Microsoft的.NET Framework 2.0在其集合基類中提供了二分查找演算法的靜態泛型版本，例如`System.Array`的`BinarySearch<T>(T[] array, T value)`方法。
- 對於Objective-C，Cocoa框架在Mac OS X 10.6及以上版本中提供了`[https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: NSArray -indexOfObject:inSortedRange:options:usingComparator:]`方法；蘋果的Core Foundation C框架也包含`[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]`函數。
- Python提供了模塊`bisect`，在插入元素後仍能保持列表的有序狀態，而無需每次插入元素後都對列表排序。
- Ruby的Array類包含帶有內置近似匹配的`bsearch`方法。
- Rust的切片原始類型提供了`binary_search()`、`binary_search_by()`、`binary_search_by_key()`、`partition_point()`方法。

## 外部連結

- 該論文內容取自英語維基百科的對應條目，於2018年經過外部學術同行評審。
- NIST Dictionary of Algorithms and Data Structures: binary search
- Comparisons and benchmarks of a variety of binary search implementations in C

## 基本資料

- 車輛類別：搜索算法
- data：陣列
- 時間：$O(\log n)$
- 容積、佔地面積：$O(1)$
- best-time：$O(1)$
- average-time：$O(\log n)$
- var1：$n$
- def1：陣列元素個數
- optimal：是