二分搜尋

二分搜尋
概況
類別	搜尋演算法
資料結構	陣列
複雜度
平均時間複雜度	$O(\log n)$
最壞時間複雜度	$O(\log n)$
最佳時間複雜度	$O(1)$
空間複雜度	疊代：$O(1)$ 遞歸：$O(\log n)$ （無尾呼叫消除）
最佳解	Yes
相關變數的定義

在電腦科學中，二分搜尋演算法（英語：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 版本- 遞歸

int binary_search(const int arr[], int start, int end, int key) {
	if (start > end)
		return -1;

	int mid = start + (end - start) / 2;    //直接平均可能會溢位，所以用此算法
	if (arr[mid] > key)
		return binary_search(arr, start, mid - 1, key);
	else if (arr[mid] < key)
		return binary_search(arr, mid + 1, end, key);
	else
	    return mid;        //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}

C 版本- while 迴圈

int binary_search(const int arr[], int start, int end, int key) {
    int ret = -1;       // 未搜索到数据返回-1下标
    
	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
		if (arr[mid] < key)
			start = mid + 1;
		else if (arr[mid] > key)
			end = mid - 1;
		else {            // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於
			ret = mid;  
            break;
        }
	}
	
	return ret;     // 单一出口
}

JavaScript 版本

var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15, 19, 20];
const binarySearch = (arr, target) => {
  const search = (start, end) => {
    if (start > end) return -1;
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] > target) {
      return search(0, mid - 1);
    } else if (arr[mid] < target) {
      return search(mid + 1, end);
    } else {
      return mid;
    }
  }
  return search(0, arr.length - 1);
}
console.log( binarySearch(arr, 4) );

Python3 版本 while 迴圈

def binary_search(arr, left, right, key):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            left = mid + 1
        elif arr[mid] > key:
            right = mid - 1
    return -1

Python3 版本 遞歸

def binary_search(arr, start, end, key):
	if start > end:
		return -1
	mid = start + (end - start) // 2
	if arr[mid] > key:
		return binary_search(arr, start, mid - 1, key)
	if arr[mid] < key:
		return binary_search(arr, mid + 1, end, key)
	return mid

C# 版本

static int binary_search(int[] arr, int start, int end, int key)
{
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (arr[mid] < key)
            start = mid + 1;
        else if (arr[mid] > key)
            end = mid - 1;
        else
            return mid; 
    }
    return -1;
}

Swift 版本

import Foundation
/// 二分搜索完全匹配
///
/// - Parameters:
///   - arr: 有序数组
///   - start: 起始位置
///   - end: 结束点
///   - key: 特点目标值
/// - Returns: 返回查找结果
func binarySearch(arr: [Int], start: Int, end: Int, key: Int) -> Int? {
    if start > end {
        return nil
    }
    let mid = start + (end - start) / 2
    if arr[mid] > key {
        return binarySearch(arr: arr, start: start, end: mid - 1, key: key)
    } else if arr[mid] < key {
        return binarySearch(arr: arr, start: mid + 1, end: end, key: key)
    } else {
        return mid
    }
}

golang 遞歸版本

func binary_search(arr []int, low, high, key int) int {
	if low > high {
		return -1
	}
	mid := low + (high-low)/2

	if arr[mid] > key {
		return binary_search(arr, low, mid-1, key)
	} else if arr[mid] < key {
		return binary_search(arr, mid+1, high, key)
	}

	return mid
}

golang 非遞歸版本

func binarySearch(arr []int, key int) int {
    low, high := 0, len(arr)-1
	for low <= high {
		mid := low + (high-low)/2
		if arr[mid] == key {
			return mid
		} else if key < arr[mid] {
			high = mid - 1
		} else if key > arr[mid] {
			low = mid + 1
		}
	}
	return -1
}

Java 遞歸

public static int binarySearch(int[] arr, int start, int end, int key){
    if (start > end)
        return -1;

    int mid = start + (end - start)/2;    //防止溢位
    if (arr[mid] > key)
        return binarySearch(arr, start, mid - 1, key);
    if (arr[mid] < key)
        return binarySearch(arr, mid + 1, end, key);
    return mid;  

}

Java while 迴圈

public static int binarySearch(int[] arr, int start, int end, int key){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > key)
            end = mid - 1;
        else if (arr[mid] < key)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }

    return result;

}

Julia版本

# Julia Sample : BinarySearch
function BinarySearch(A,Key)
	left,right = 1,length(A)

	while(left<=right)
		mid=left+floor(Int,((right-left)/2))
	
		if A[mid]==Key
			return mid
		elseif Key<A[mid]
			right = mid-1
		elseif Key>A[mid]
			left = mid+1
		end
	end
	return -1
end

# Main Code
A = [1,3,16,31,43,354,586]   # Already Arrange
println(A)                   # Original Array
println(BinarySearch(A,43))  # BinarySearch Search Array
println(BinarySearch(A,354)) # BinarySearch Search Array
println(BinarySearch(A,3))   # BinarySearch Search Array

歷史

在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（頁面存檔備份，存於互聯網檔案館）