バイナリナビゲーション

バイナリナビゲーション
バイナリ検索は、配列内部のデータをソートする必要があるアルゴリズムです.
データはランダムに使用できませんが、ソートされている場合、すぐにデータを見つけることができるのが特徴です.半分の範囲を縮小し、データを探索する特徴がある.
バイナリ・ナビゲーションでは、ナビゲーションする範囲の始点、終点、中点の3つの位置を表す変数が使用されます.
検索するデータを中間位置のデータと繰り返し比較して、必要なデータを検索します.
バイナリ探索の時間的複雑度はO(logn)であり,確認されるたびに元素数が半分に減少するためである.
バイナリ探索を実現する方法は2つある.1つは再帰関数を利用する方法であり,もう1つは重複文を簡単に利用する方法である.
繰り返し文の使用方法

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

再帰関数の使用方法

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

符号化テストのバイナリルックアップ問題は,ルックアップ範囲が大きい場合にルックアップを行うと仮定する問題が多い.したがって,ナビゲーションの範囲が1000万単位を超えると,バイナリナビゲーションのようにO(logn)の速度を速める.