Javaを使用して二分探索を実行する方法

2 分法探索（バイナリサーチ）とは、並び順が決められた配列やリストに対して使われる、よく利用される探索アルゴリズムです。その基本思想は、探索範囲を 2 つに分け、ターゲットとなる値と中間要素を比べます。等しければ中間要素の場所を返し、ターゲットとなる値が中間要素より小さければ左半分で探索を続け、大きければ右半分で探索を続けます。ターゲットとなる値がみつかるか探索範囲が空になるまで続けます。

次以下にJavaで2分探索法を実装したサンプルコードを示します。

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 - left) / 2;

            // 目标值与中间元素相等，返回中间元素的位置
            if (arr[mid] == target) {
                return mid;
            }

            // 目标值小于中间元素，在左半部分继续查找
            if (arr[mid] > target) {
                right = mid - 1;
            }
            
            // 目标值大于中间元素，在右半部分继续查找
            else {
                left = mid + 1;
            }
        }

        // 查找区间为空，未找到目标值
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("目标值在数组中的位置为：" + result);
        } else {
            System.out.println("目标值在数组中未找到");
        }
    }
}

与えられたサンプルコードでは、binarySearchメソッドは、ソートされた配列とターゲット値を引数として受け取り、leftとrightという2つのポインタを使用して、検索範囲の左境界と右境界を表します。各反復処理で、中間位置midを計算し、ターゲット値との比較を行い、比較結果に基づいて左右境界を調整し、最終的にターゲット値の位置を特定するか、ターゲット値が存在しないことを確認します。mainメソッドでは、ソートされた配列arrとターゲット値targetを定義し、binarySearchメソッドを呼び出して検索を実行し、ターゲット値が配列内の位置または見つからなかったというヒントメッセージを出力します。