アルゴリズム-二分探索アルゴリズム

アルゴリズム:二分探索アルゴリズム(折半探索アルゴリズム)時間複雑度:

二分探索アルゴリズム概要

二分探索アルゴリズム擬似コード

二分探索アルゴリズム実現

二分探索アルゴリズムの概要
二分探索アルゴリズムは、折半探索アルゴリズムとも呼ばれ、すなわち、1つの秩序配列内で特定の要素を検索する.検索プロセス全体が中間から始まり、検索する要素が中間要素である場合、検索プロセスは終了します.逆に、中間要素と検索する要素の関係に基づいて、配列に対応する半分を検索します.例えば、検索要素が中間要素より大きい場合、配列全体の大きな要素の半分を検索し、要素が見つかるまで、または配列が空で、要素が見つからないまで、このプロセスを繰り返します.
二分探索アルゴリズムの説明
配列A_0,A_1...A_{n-1}A_0 \le A_1 \le \cdot \le A_{n - 1}が与えられ、検索される要素はsearchnumである.

はleftrightでそれぞれ左右の端点、すなわち検索する範囲を表す.

はmiddleで中間点を表し、middle = \lfloor (left + right) / 2 \rfloorである.

left > rightの場合、検索に失敗します.

A{middle} > searchnumright = middle - 1なら、3を返します.

A{middle} < searchnumleft = middle + 1なら、3を返します.

A{middle} = searchnumの場合、検索は終了し、middleに戻る.

二分探索アルゴリズム擬似コード
while実装
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

再帰的な実装
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

二分ルックアップアルゴリズム実装
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;

参考資料

『データ構造基礎(C言語版)』第2版

二分検索アルゴリズム-ウィキペディア、フリー百科事典

本文は個人のブログのアルゴリズム-二分の検索のアルゴリズム|存在しない猫に先発して、転載して出典を明記して下さい