折半搜索算法

在電腦科學中，**二分搜尋演算法**（英語：binary search algorithm），也稱**折半搜尋演算法**（英語：half-interval search algorithm）、**對數搜尋演算法**（英語：logarithmic search algorithm），是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。

二分搜尋演算法在最壞情況下是對數時間複雜度的，需要進行 $O(\log n)$ 次比較操作（ $n$ 在此處是陣列的元素數量， $O$ 是大 O 記號， $\log $ 是對數）。二分搜尋演算法使用常數空間，對於任何大小的輸入資料，演算法使用的空間都是一樣的。除非輸入資料數量很少，否則二分搜尋演算法比線性搜尋更快，但陣列必須事先被排序。儘管一些特定的、為了快速搜尋而設計的資料結構更有效（比如雜湊表），二分搜尋演算法應用面更廣。

二分搜尋演算法有許多種變種。比如分散層疊可以提升在多個陣列中對同一個數值的搜尋的速度。分散層疊有效的解決了計算幾何學和其他領域的許多搜尋問題。指數搜尋將二分搜尋演算法拓寬到無邊界的列表。二元搜尋樹和 B 樹資料結構就是基於二分搜尋演算法的。

## 演算法

二分搜尋只對有序陣列有效。二分搜尋先比較陣列中位元素和目標值。如果目標值與中位元素相等，則返回其在陣列中的位置；如果目標值小於中位元素，則搜尋繼續在前半部分的陣列中進行。如果目標值大於中位元素，則搜尋繼續在陣列上部分進行。由此，演算法每次排除掉至少一半的待查陣列。

### 步驟

給予一個包含 $n$ 個帶值元素的陣列 $A$ 或是記錄 $A_{0},\cdots ,A_{n-1}$ ，使 $A_{0}\leq \cdots \leq A_{n-1}$ ，以及目標值 $T$ ，還有下列用來搜尋 $T$ 在 $A$ 中位置的子程式。

1. 令 $L$ 為 $0$ ， $R$ 為 $n-1$ 。
2. 如果 $L>R$ ，則搜尋以失敗告終。
3. 令 $m$ （中間值元素）為 $\lfloor (L+R)/2\rfloor $ 。（具體實現中，為防止算術溢位，一般採用 $\lfloor L+(R-L)/2\rfloor $ 代替。）
4. 如果 $A_{m}<T$ ，令 $L$ 為 $m+1$ 並回到步驟二。
5. 如果 $A_{m}>T$ ，令 $R$ 為 $m-1$ 並回到步驟二。
6. 當 $A_{m}=T$ ，搜尋結束；回傳值 $m$ 。

這個疊代步驟會持續透過兩個變數追蹤搜尋的邊界。有些實際應用會在演算法的最後放入相等比較，讓比較迴圈更快，但平均而言會多一層疊代。

### 大致匹配

以上程式只適用於_完全_匹配，也就是尋找一個目標值的位置。不過，因為有序陣列的順序性，將二分搜尋演算法擴展到能適用大致匹配並不是很重要。舉例來說，二分搜尋演算法可以用來計算一個賦值的**排名**（或稱**秩**，比它更小的元素的數量）、**前趨**（下一個最小元素）、**後繼**（下一個最大元素）以及**最近鄰**。搜尋兩個值之間的元素數目的範圍查詢可以藉由兩個排名查詢（又稱**秩查詢**）來執行。

* 排名查詢可以使用調整版的二分搜尋來執行。藉由在成功的搜尋回傳 $m$ ，以及在失敗的搜尋回傳 $L$ ，就會取而代之地回傳了比起目標值小的元素數目。
* 前趨和後繼查詢可以藉由排名查詢來執行。一旦知道目標值的排名，其前趨就會是那個位於其排名位置的元素，或者排名位置的上一個元素（因為它是小於目標值的最大元素）。其後繼是（陣列中的）下一個元素，或是（非陣列中的）前趨的下一個元素。目標值的最近鄰可能是前趨或後繼，取決於何者較為接近。
* 範圍查詢也是直接了當的。一旦知道兩個值的排名，不小於第一個值且小於第二個值的元素數量就會是兩者排名的差。這個值可以根據範圍的端點是否算在範圍內，或是陣列是否包含其端點的對應鍵來增加或減少 1。

## 複雜度分析

**時間複雜度**
: 折半搜尋每次把搜尋區域減少一半，時間複雜度為 $O\left(\log n\right)$ 。（n 代表集合中元素的個數）

**空間複雜度**
: $O\left(1\right)$ 。雖以遞迴形式定義，但是尾遞迴，可覆寫為迴圈。

## 應用

除直接在一個陣列中搜尋元素外，可用在插入排序中。

## 範例代碼

### C 版本 - 遞迴

### C 版本 - while 迴圈

### javascript 版本

### Python3 版本 while 迴圈

### Python3 版本 遞迴

 

### C# 版本

1. this is c++

### Swift 版本

### golang 遞迴版本

### golang 非遞迴版本

### Java 遞迴

### Java while 迴圈

### Julia (程式語言)

## 歷史

在 1946 年，約翰・莫奇利在摩爾學院講座上第一次提出二分搜尋的概念。1957 年，威廉・皮特遜發表了第一個應用插值搜尋的演算法。在此時，每個發表的二分搜尋演算法只對長度為 2 的冪減一的陣列有用。直到 1960 年，德里克・亨利・萊默發表了一個對於所有長度的陣列都適用的演算法。1962 年，赫爾曼・博滕布魯赫發表了一個用 ALGOL 60 寫的二分搜尋，將判斷相等的步驟放到演算法末尾。雖然將平均疊代次數增加一，但是每次疊代中的比較次數減少了 1 次。均勻二分搜尋則是史丹佛大學的 A. K. 錢德拉在 1971 年發明的。1986 年，伯納德・查澤爾和列奧尼達斯・吉巴斯引入了分散層疊來解決計算幾何中大量存在的搜尋問題。

## 實現中的問題

> 
> 儘管二分搜尋的基本思想相對簡單，但細節可以令人難以招架 ... — 高德納
> 
> 

當喬恩・本特利將二分搜尋問題布置給專業編程課的學生時，百分之 90 的學生在花費數小時後還是無法給出正確的解答，主要因為這些錯誤程式在面對邊界值的時候無法執行，或返回錯誤結果。1988 年開展的一項研究顯示，20 本教科書里只有 5 本正確實現了二分搜尋。不僅如此，本特利自己 1986 年出版的《編程珠璣》一書中的二分搜尋演算法存在整數溢位的問題，二十多年來無人發現。Java 語言的庫所實現的二分搜尋演算法中同樣的溢位問題存在了九年多才被修復。

## 參考

## 外部連結

* NIST Dictionary of Algorithms and Data Structures: binary search（頁面存檔備份，存於網際網路檔案館）
* Google Research: Nearly All Binary Searches and Mergesorts are Broken（頁面存檔備份，存於網際網路檔案館）.
* Binary search implemented in 12 languages（頁面存檔備份，存於網際網路檔案館）.
* 程式設計師編程藝術第二十五章：Jon Bentley：90% 無法正確實現二分搜尋（頁面存檔備份，存於網際網路檔案館）
* https://leetcode.com/explore/learn/card/binary-search（頁面存檔備份，存於網際網路檔案館）