二分搜尋算法

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

基本介紹

• 中文名：二分搜尋
• 外文名：binary search
• 又稱：折半搜尋、對數搜尋
• 類別：一種搜尋算法
• 數據結構：數組

原理

計算步驟

給予一個包含 個帶值元素的數組 或是記錄，使 ，以及目標值 ，還有下列用來搜尋 在 中位置的子程式。

令 為 ， 為 。

如果 ，則搜尋以失敗告終。

令 （中間值元素）為 。

如果 ，令 為 並回到步驟二。

如果 ，令 為 並回到步驟二。

當 ，搜尋結束；回傳值 。

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

大致匹配

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

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

複雜度分析

• 時間複雜度
  

折半搜尋每次把搜尋區域減少一半，時間複雜度為 。（n代表集合中元素的個數）

• 空間複雜度
  

，雖以遞歸形式定義，但是尾遞歸，可改寫為循環。

示例代碼

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 版本

Array.prototype.binary_search = function(low, high, khey) {if (low > high)return -1;var mid = parseInt((high + low) / 2);if (this[mid] > khey)return this.binary_search(low, mid - 1, khey);if (this[mid] < khey)return this.binary_search(mid + 1, high, khey);return mid;};

Python3 版本 遞歸

def binary_search(arr,start,end,hkey):if start > end:return -1mid = start + (end - start) / 2if 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

Python3 版本 while 循環

def binary_search(arr, start, end, hkey):while start <= end:mid = start + (end - start) // 2if arr[mid] < hkey:start = mid + 1elif arr[mid] > hkey:end = mid - 1else: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? {    guard start < end else {        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    }}

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 循環

```Java 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; }