算法：二分搜索算法（折半查找算法）
時(shí)間復(fù)雜度：

• 二分搜索算法概述
• 二分搜索算法偽代碼
• 二分搜索算法實(shí)現(xiàn)

二分搜索算法概述

二分搜索算法，也稱折半查找算法，即在一個(gè)有序數(shù)組中查找某一個(gè)特定元素。整個(gè)搜索過(guò)程從中間開(kāi)始，如果要查找的元素即中間元素，那么搜索過(guò)程結(jié)束；反之根據(jù)中間元素與要查找元素的關(guān)系在數(shù)組對(duì)應(yīng)的那一半查找，例如查找元素大于中間元素，則在整個(gè)數(shù)組較大元素的那一半查找，反復(fù)進(jìn)行這個(gè)過(guò)程，直到找到元素，或者數(shù)組為空，查找不到元素。

二分搜索算法描述

給定一個(gè)數(shù)組A_0,A_1...A_{n-1}， A_0 \le A_1 \le \cdot \le A_{n - 1}，待查找元素為searchnum：

1. 用left，right分別表示左右端點(diǎn)，即要查找的范圍；
2. 用middle表示中間點(diǎn)，middle = \lfloor (left + right) / 2 \rfloor；
3. 若left > right，搜索失?。?/li>
4. 若A{middle} > searchnum，right = middle - 1，返回3；
5. 若A{middle} < searchnum，left = middle + 1，返回3；
6. 若A{middle} = searchnum，搜索結(jié)束，返回middle。

二分搜索算法偽代碼

while 實(shí)現(xiàn)

BINARY-SEARCH-WHILE(A, searchnum, left, right)

while left <= right
  middle = (left + right) div 2
  case
    A_middle < searchnum : left = middle + 1
    A_middle > searchnum : right = middle - 1
    A_middle = searchnum : return middle
return FAILED

遞歸實(shí)現(xiàn)

BINARY-SEARCH-RECURSION(A, searchnum, left, right)

if left <= right
  middle = (left + right) div 2
  case
    A_middle < searchnum :
      return (A, searchnum, middle + 1, right)
    A_middle > searchnum :
      return (A, searchnum, left, middle - 1)
    A_middle = searchnum :
      return middle

二分查找算法實(shí)現(xiàn)

C

while 版本

int binarySearch(arrType * a, arrType searchnum, int left, int right)
{
    int middle;
    while (left <= right) {
        middle = (left + right) / 2;
        if (a[middle] > searchnum)
            right = middle - 1;
        else if (a[middle] < searchnum)
            left = middle + 1;
        else if (a[middle] == searchnum)
            return middle;
    }
    return -1;
}

遞歸版本

int binarySearch(arrType * a, arrType searchnum, int left, int right)
{
    int middle;
    if (left <= right) {
        middle = (left + right) / 2;
        if (a[middle] > searchnum)
            return binarySearch(a, searchnum, left, middle - 1);
        else if (a[middle] < searchnum)
            return binarySearch(a, searchnum, middle + 1, right);
        else if (a[middle] == searchnum)
            return middle;
    }
    return -1;
}

Pascal

外部定義全局變量：

var
    a : array[1..n] of integer;
    searchnum, result :integer;

while 版本

procedure binarySearch(left, right :integer);
var
    middle : integer;
begin
    while (left <= right) do
        begin
            middle := (left + right) div 2;
            if (a[middle] > searchnum) then
                right := middle  - 1
            else if (a[middle] < searchnum) then
                left := middle + 1
            else
                begin
                    result := middle;
                    break;
                end;
        end;
    if left > right then
        result := -1;
end;

遞歸版本

procedure binarySearch(left, right :integer);
var
    middle : integer;
begin
    if left <= right then
        begin
            middle := (left + right) div 2;
            if (a[middle] > searchnum) then
                binarySearch(left, middle - 1)
            else if (a[middle] < searchnum) then
                binarySearch(middle + 1, right)
            else
                result := middle;
        end
    else
        result := -1;
end;

參考資料

• 《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語(yǔ)言版）》第二版
• 二分搜索算法 - 維基百科，自由的百科全書

本文首發(fā)于個(gè)人博客算法 - 二分搜索算法 | 不存在的貓， 轉(zhuǎn)載請(qǐng)注明出處