1概要

この記事では、単純な線形検索よりも二分検索の利点について説明し、Javaでの実装について説明します。

私たちはワイン販売事業に従事しており、何百万ものバイヤーが毎日私たちのアプリケーションを訪れているとしましょう。

私たちのアプリを通して、顧客は

n

ドルを下回る価格を持つアイテムを除外し、検索結果からボトルを選択して、それらを自分のカートに追加することができます。私たちは毎秒何百万ものユーザーに価格制限のあるワインを探しています。結果は速い必要があります。

バックエンドでは、私たちのアルゴリズムは、顧客によって入力された価格制限をリスト内のすべてのワインボトルの価格と比較して、ワインのリスト全体にわたって線形検索を実行します。

それから、それは価格限界以下の価格を持つアイテムを返します。この線形検索は、

O(n)

という時間の複雑さを持っています。

これは、システム内のワインボトルの数が多いほど、時間がかかることを意味します。 ** 検索時間は、導入された新しいアイテムの数に比例して長くなります。

ソートされた順序でアイテムの保存を開始し、バイナリ検索を使用してアイテムを検索すると、複雑な

O(log n)

を達成できます。

バイナリ検索では、検索結果にかかる時間はデータセットのサイズに比例して増加しますが、比例的には増加しません。


3バイナリ検索

簡単に言うと、アルゴリズムは

key

値を配列の中央の要素と比較します。それらが等しくない場合、キーが含まれることができない半分は排除され、それが成功するまで残りの半分について検索が続けられる。

覚えておいてください – ここでの重要な側面は、配列がすでにソートされているということです。

残りの半分が空になって検索が終了した場合、

key

は配列内にありません。


3.1. 反復含意

public int runBinarySearchIteratively(
  int[]sortedArray, int key, int low, int high) {
    int index = Integer.MAX__VALUE;

    while (low <= high) {
        int mid = (low + high)/2;
        if (sortedArray[mid]< key) {
            low = mid + 1;
        } else if (sortedArray[mid]> key) {
            high = mid - 1;
        } else if (sortedArray[mid]== key) {
            index = mid;
            break;
        }
    }
    return index;
}


runBinarySearchIteratively

メソッドは

sortedArray



key

を取ります。


middle



sortedArray

の中間インデックスです。これで、アルゴリズムは

key



sortedArray

の中間インデックスの配列値と比較して

while

ループを実行します。


3.2. 再帰的Impl

それでは、単純で再帰的な実装についても見てみましょう。

public int runBinarySearchRecursively(
  int[]sortedArray, int key, int low, int high) {
    int middle = (low + high)/2;

    if (high < low) {
        return -1;
    }

    if (key == sortedArray[middle]) {
        return middle;
    } else if (key < sortedArray[middle]) {
        return runBinarySearchRecursively(
          sortedArray, key, low, middle - 1);
    } else {
        return runBinarySearchRecursively(
          sortedArray, key, middle + 1, high);
    }
}


runBinarySearchRecursively

メソッドは、

sortedArray



sortedArray



key、

low、および

high

インデックスを受け入れます。


3.3.

Arrays.binarySearch()


を使う

int index = Arrays.binarySearch(sortedArray, key);

整数の配列内で検索される

A sortedArray



int


key

は、引数としてJava

Arrays

クラスの

binarySearch

メソッドに渡されます。


3.4.

Collections.binarySearch()


を使用する

int index = Collections.binarySearch(sortedList, key);


ソートリスト


3.5. パフォーマンス

  • アルゴリズムを書くために再帰的アプローチを使用するか反復的アプローチを使用するかは、ほとんど個人的な好みの問題です** しかし、ここでも注意すべきいくつかの点があります。

{空} 1再帰は

stack

を維持するためのオーバーヘッドのために遅くなる可能性があり、通常はより多くのメモリを消費します+2。ビッグデータセット+ 3を処理するときに

StackOverflowException

が発生する可能性があります。反復は反復アプローチに比べてコードが短くなるため、コードに明確さが追加されます

理想的には、大きなnの値に対する線形検索とは対照的に、二分検索はより少ない数の比較を実行するでしょう。 nの値が小さいと、線形検索の方が二分検索よりもパフォーマンスが向上します。

この分析は理論的なものであり、状況によって異なる可能性があることを知っておく必要があります。

また、バイナリ検索アルゴリズムはソートされたデータセットを必要とし、そのコストもかかります。データをソートするためにマージソートアルゴリズムを使用すると、コードにさらに複雑な

n log n

が追加されます。

そのため、最初に要件をよく分析してから、どの検索アルゴリズムが要件に最も適しているかを判断する必要があります。


4結論

このチュートリアルでは、バイナリ検索アルゴリズムの実装と、線形検索ではなくそれを使用することが望ましいシナリオを示しました。

チュートリアルのコードhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[over on GitHub]を見つけてください。