Javaでの二分探索アルゴリズム

投稿日: 2019-10-18 2022-10-20
タグ: Algorithms, Java, Java Search

1. 概要

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

2. 効率的な検索の必要性

私たちがワイン販売ビジネスを行っており、毎日何百万ものバイヤーが私たちのアプリケーションにアクセスしているとしましょう。

私たちのアプリを通じて、顧客は n ドル未満の価格のアイテムを除外し、検索結果からボトルを選択して、カートに追加することができます。毎秒価格制限のあるワインを求める何百万人ものユーザーがいます。結果は速い必要があります。

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

次に、価格が制限価格以下のアイテムを返します。この線形探索の時間計算量はO（n）です。

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

アイテムを並べ替えて保存し、バイナリ検索を使用してアイテムを検索すると、 O（log n）の複雑さを実現できます。

二分探索では、検索結果にかかる時間はデータセットのサイズに応じて自然に増加しますが、比例するわけではありません。

3. 二分探索

簡単に言えば、アルゴリズムは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 - low) / 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;
}

The runBinarySearchIteratively メソッドは sortedArray 、鍵＆低い＆高いのインデックス sortedArray 引数として。メソッドが初めてlowを実行するとき、 sortedArray、の最初のインデックスは0ですが、highはの最後のインデックスです。 ] sortedArray、はその長さ–1に等しくなります。

middle は、sortedArrayのミドルインデックスです。これで、アルゴリズムは while ループを実行し、keyをsortedArrayの中央インデックスの配列値と比較します。

ミドルインデックスがどのように生成されるかに注意してください（int mid = low +（（high – low）/ 2）。これは、非常に大きなアレイに対応するためです。ミドルインデックスを取得するだけでミドルインデックスが生成される場合 （int mid =（low + high）/ 2） 、2を含む配列ではオーバーフローが発生する可能性があります³⁰ 以上の要素の合計として低+高最大正を簡単に超える可能性があります int 価値。

3.2. 再帰的な実装

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

public int runBinarySearchRecursively(
  int[] sortedArray, int key, int low, int high) {
    int middle = low  + ((high - low) / 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 、 key、 low 、およびhighインデックスのsortedArrayを受け入れます。 。

3.3. 配列の使用。binarySearch（）

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

sortedArrayとint key は、整数の配列で検索され、binarySearchメソッドに引数として渡されます。 Java Arraysクラスの

3.4. コレクションの使用。binarySearch（）

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

ソートされたリスト ＆整数鍵、のリストで検索されます整数オブジェクトは、引数としてに渡されます binarySearch Javaのメソッドコレクションクラス。

3.5. パフォーマンス

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

1. スタックを維持するオーバーヘッドのために再帰が遅くなる可能性があり、通常はより多くのメモリを消費します2。再帰はスタック-フレンドリーではありません。ビッグデータセット3を処理するときにStackOverflowExceptionが発生する可能性があります。再帰は、反復アプローチと比較してコードを短くするため、コードに明確さを追加します

理想的には、nの大きな値の線形検索とは対照的に、バイナリ検索はより少ない数の比較を実行します。 nの値が小さい場合、線形検索は2分検索よりもパフォーマンスが向上する可能性があります。

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

また、二分探索アルゴリズムには、コストもかかるソートされたデータセットが必要です。データの並べ替えにマージ並べ替えアルゴリズムを使用する場合、 n lognの複雑さがコードに追加されます。

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

4. 結論

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

チュートリアルのコードはGitHubで見つけてください。

getdocs

13036