Javaを使用して二分探索アルゴリズムを実装する方法

Java を使用してバイナリ検索アルゴリズムを実装する方法

バイナリ検索アルゴリズムは、ソートされた配列に適した効率的な検索方法です。基本的な考え方は、検索範囲を継続的に絞り込み、検索値と配列の中央の要素を比較し、比較結果に基づいて目的の要素が見つかるまで左半分を検索し続けるか右半分を検索し続けるかを決定することです。検索範囲が空になります。

Java で二分探索アルゴリズムを実装する方法を詳しく紹介します。

ステップ 1: バイナリ検索メソッドを実装する

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

ステップ 2: バイナリ検索メソッドをテストする

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为：" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

上記のコードは、まず BinarySearch クラスを定義します。ここには、二分探索アルゴリズムを実装するための静的メソッド binarySearch が含まれています。 binarySearch メソッドでは、検索範囲の左端と右端の要素をそれぞれ指す 2 つのポインター left と right を定義します。ループ内で、中央要素 mid のインデックスが計算され、ルックアップ値が arr[mid] と比較されます。 2 つが等しい場合、ターゲット要素が見つかり、そのインデックス値 mid が返されることを意味します。検索値が arr[mid] より大きい場合は、left ポインタを 1 つ右に移動し、検索範囲を右半分に狭めます。検索値が arr[mid] 未満の場合は、right ポインタを 1 つ左に移動し、検索範囲を左半分に絞ります。ループは、目的の要素が見つかるか、検索範囲が空になるまで継続されます。ループ終了後にターゲット要素が見つからなかった場合は、見つからなかったことを示す -1 が返されます。

Main クラスの main メソッドで、ソートされた配列 arr と検索対象のターゲット要素 target を作成します。 。次に、BinarySearch クラスの binarySearch メソッドを呼び出してバイナリ検索を実行し、返された結果を index 変数に保存します。最後に、返された結果に基づいて目的の要素が見つかったかどうかが判断され、対応する結果が出力されます。

上記のコード例を通して、Java での二分探索アルゴリズムの実装は非常に簡単で、完了するには数行のコードのみが必要であることがわかります。この方法の検索時間の複雑さは O(logn) であり、非常に効率的であり、大規模なソートされた配列に適しています。複数の検索操作が必要な場合は、効率を向上させるために配列の並べ替え操作を個別に分割できます。

この記事が二分探索アルゴリズムの理解と使用に役立つことを願っています。

以上がJavaを使用して二分探索アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。