バイナリナビゲーションアルゴリズム

バイナリナビゲーション

バイナリ検索は、ソートされたレコードに必要な値を含むインデックスを検索するアルゴリズムです.分割征服方式のアルゴリズムとしては,最悪の場合O(logn)速度を持つアルゴリズムである.
分割征服(Divide and Conquer)はアルゴリズム中の問題を小部分に分割して解決する小部分問題であり,元の問題サイズを結合して問題を解決する方式である.

動作原理

まず、ソートされたレコードから中央値を選択します.

の中間値と検索値を比較します.

以降

の中間値>ルックアップ値の場合、中間値より大きいレコードでバイナリ検索が繰り返されます.

中間値<ルックアップ値の場合は、中間値より小さいレコードでバイナリ検索を繰り返します.

の中間値==検索値の場合、中間値が返され、関数が終了します.

大きな値または小さな値のレコードが含まれていない場合は、-1を返して終了します.

コード#コード#

c++

#include<iostream>
#include<vector>

using namespace std;

int BinarySearch(vector<int> arr, int target, int high, int low)
{
    // 중간 값을 찾는다.
    int mid = (high + low)/2;

    // 전체 종료 조건 1( 전체 레코드에서 값이 없을 때)
    if(low > high)
        return -1;

    // 전체 종료 조건 2( 값을 찾았을 때)
    if(arr[mid] == target){
        return mid;
    }

    // 중간 값이 클 때
    else if(arr[mid] > target){
        return BinarySearch(arr, target, high, mid+1);
    }

    //  중간 값이 작을 때
    else if(arr[mid] < target){
        return BinarySearch(arr, target, mid-1, low);
    }
}

実際の操作

昇順に並べられたレコードがあります.
1, 10, 25, 40, 59, 100, 200, 312
この配列で200の値を検索します.

初めての試み

まず、中間の任意の値40が選択される.
選択した値40と検索する値200とを比較します.
選択した値は40より大きい.40より右側の59, 100, 200, 312です.
バイナリ探索を行う.

2回目の試み

59, 100, 200, 312
中間の任意の値100を選択します.
選択された値100は、検索する値200よりも小さい.
比100の右側にある200, 312の値を用いてバイナリ探索を行った.

3回目の試み

200, 312
2つのオプションから小さい値を選択します.200を選択します.200は、検索する値に等しいです.
は、200のインデックス6を返し、関数は終了します.

最悪の場合の回数を計算する

記録パッチナビゲーションバイナリナビゲーション101041007100010001010000001000014
1つずつ探す線形探索が線形に回数を増やすと,バイナリ探索はlog的に増加するので回数は多く増加しないことがわかる.