C言語版二分検索アルゴリズム


二分探索アルゴリズムは秩序配列において使用する比較的頻繁なアルゴリズムであり、二分探索アルゴリズムに接触していない場合、最も一般的な方法は配列を遍歴し、各要素と比較し、その時間はO(n)である.しかし、二分ルックアップアルゴリズムは、そのルックアップ時間がO(lgn)であるため、例えば配列{1,2,3,4,5,6,7,8,9}のように、要素6をルックアップし、二分ルックアップアルゴリズムで実行すると、その順序は:1である.第1のステップは中間要素、すなわち5を検索し、5<6のため、6は必然的に5の後の配列要素の中で、{6,7,8,9}の中で検索し、2.{6,7,8,9}の中位数を探して、7,7>6で、6は7の左側の配列要素の中にあるべきで、それでは6だけ残って、すぐ見つかりました.
二分ルックアップアルゴリズムは,配列を絶えず半分割し,中間要素とgoalを毎回比較する.
#include <iostream>
using namespace std;

//    
int binary_search(int* a, int len, int goal);

int main()
{
    const int LEN  = 10000;
    int a[LEN];
    for(int i = 0; i < LEN; i++)
        a[i] = i - 5000;
    int goal = 0;
    int index = binary_search(a, LEN, goal);

    if(index != -1)
        cout<<goal<<"        "<<binary_search(a, LEN, goal)<<endl;
    else
        cout<<"   "<<goal<<endl;
    return 0;
}

int binary_search(int* a, int len, int goal)
{
    int low = 0;
    int high = len - 1;
    while(low <= high)
    {
        int middle = (low + high)/2;
        if(a[middle] == goal)
            return middle;
        //    
        else if(a[middle] > goal)
            high = middle - 1;
        //    
        else
            low = middle + 1;
    }
    //   
    return -1;
}