二分搜索算法

演算法

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

應用

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

C 版本- 遞迴

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

int mid = start + (end - start) / 2;    //直接平均可能會溢位，所以用此算法
if (arr[mid] > khey)
return binary_search(arr, start, mid - 1, khey);
else if (arr[mid] < khey)
return binary_search(arr, mid + 1, end, khey);
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];function binarySearch (arr, val) {
    var low = 0,
        high = arr.length - 1;
    while (low <= high) {
        var mid = parseInt( (low + high) / 2 );
        if (val == arr[mid]) {
            return mid;
        }else if (val > arr[mid]) {
            low = mid + 1;
        }else if (val < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1;};  
console.log( binarySearch(arr, 4) );

Python3 版本 while 迴圈

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

Python3 版本 遞迴

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

C# 版本

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

Swift 版本

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

golang 遞迴版本

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

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

return mid}

golang 非遞迴版本

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

Java 遞迴

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

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

}

Java while 迴圈

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

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

    return result;}

歷史

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

實現中的問題

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