卒業生は就職活動のためにアルゴリズムを知っておく必要があります。バイナリ検索をステップバイステップで教えます

1. 二分探索の背景

配列またはコレクションに多数の要素が格納されている場合、特定の要素の位置または存在を追跡したい場合、従来の方法は、探している要素が見つかるまで各要素をループすることです。この検索方法は非常に非効率なので、検索効率を向上させるにはバイナリ検索が必要です。

2. 二分探索入門

指定された値の位置を見つけるための二分探索（半探索）

Baidu 百科事典では二分探索を次のように紹介しています。

3. 二分探索のアルゴリズムの考え方

配列が昇順でソートされていると仮定すると、指定されたターゲット値目標に対して、配列の中央から検索を開始します。1. 検索データが中央の要素値と正確に等しい場合は、中央の要素値のインデックスを返します。2. 検索値が中央の値より小さい場合は、検索範囲全体の前半を新しい検索範囲として使用します。3. 検索値が中央の値より大きい場合は、検索範囲全体の後半を新しい検索範囲として使用します。注: 検索が成功した場合はインデックスが返され、失敗した場合は -1 が返されます。

4. コードの実装

4.1 ループを使用して二分探索を実装する

パブリッククラスBinarySearch {
公共 静的void main(String[] args) {
        // ランダム配列を生成する
int [] 配列 = suiji();
        // ランダム配列をソートする
        配列.sort(配列);
        System.out.println ( "生成されたランダム配列は次のとおりです:" + Arrays.toString(array)); 
 
        System.out.println ( "検索する値:" );
        スキャナー入力 = new Scanner(System.in ) ;
        // 検索するターゲット値
int目的 = input.nextInt(); 
 
        // バイナリ検索を使用する
整数 インデックス= binarySearch(配列、目的);
        System.out.println ( "検索対象の値のインデックス位置:" + index ); 
 
    } 
 
    /**
     * ランダム配列を生成する
     *
     * @return戻り値、ランダムな配列を返す
     */
    プライベートスタティック  int [] スイジ() {
        // random.nextInt(n)+m は m から m+n-1 の間の乱数を返します
int n = 新しいRandom().nextInt(6) + 5;
 int [] 配列 = 新しいint [n];
        // 配列をループして値を割り当てる
( int i = 0; i < 配列の長さ; i++) {
            配列[i] = 新しいRandom().nextInt(100);
        }
配列を返します。
    } 
 
    /**
     * 二分探索--- ループで実装 
     *
     * @param array 検索する配列
     * @param aim 探す値
     * @return戻り値、成功した場合はインデックスを返し、失敗した場合は -1 を返します
     */
    プライベートスタティック  intバイナリサーチ( int [] 配列, int目的) {
        // 配列の最小インデックス値
整数 左= 0;
        // 配列の最大インデックス値
整数 右= 配列の長さ - 1;
整数中間;
        （左<=右）{
            中央 = (左+右) / 2;
            // 検索値が中央値より小さい場合、検索範囲全体の前半が新しい検索範囲として使用されます
            if (目的 < 配列[mid]) {
右= 中央 - 1;
                // 検索値が中央値より大きい場合、検索範囲全体の後半部分が新しい検索範囲として使用されます
            }そうでない場合 (aim > array[mid]) {
左= 中央 + 1;
                // 検索されたデータが中央の要素の値と完全に等しい場合は、中央の要素の値のインデックスを戻します
            }それ以外{
ミッドに戻ります。
            }
        }
 -1 を返します。
    }
 }

コード実行結果:

生成されたランダム配列は次の通りです: [16, 33, 40, 46, 57, 63, 65, 71, 85]
検索する値:
 46
検索する値のインデックス位置: 3

入力値が見つからない場合は -1 が返されます。

生成されたランダム配列は次の通りです: [28, 41, 47, 56, 70, 81, 85, 88, 95]
検索する値:
 66
検索する値のインデックス位置: -1

4.2 再帰を用いた二分探索の実装

パブリッククラスBinarySearch2 {
公共 静的void main(String[] args) {
        // ランダム配列を生成する
int [] 配列 = suiji();
        // ランダム配列をソートする
        配列.sort(配列);
        System.out.println ( "生成されたランダム配列は次のとおりです:" + Arrays.toString(array)); 
 
        System.out.println ( "検索する値:" );
        スキャナー入力 = new Scanner(System.in ) ;
        // 検索するターゲット値
int目的 = input.nextInt(); 
 
        // バイナリ検索を使用する
整数 インデックス= binarySearch(配列、目標、0、配列の長さ - 1);
        System.out.println ( "検索対象の値のインデックス位置:" + index );
    } 
 
    /**
     * ランダム配列を生成する
     *
     * @return戻り値、ランダムな配列を返す
     */
    プライベートスタティック  int [] スイジ() {
        // Random.nextInt(n)+m は m から m+n-1 の間の乱数を返します
int n = 新しいRandom().nextInt(6) + 5;
 int [] 配列 = 新しいint [n];
        // 配列をループして値を割り当てる
( int i = 0; i < 配列の長さ; i++) {
            配列[i] = 新しいRandom().nextInt(100);
        }
配列を返します。
    } 
 
    /**
     * 二分探索--- 再帰法 
     *
     * @param array 検索する配列
     * @param aim 探す値
     * @param left左の最小値
     * @param right右側の最大値
     * @return戻り値、成功した場合はインデックスを返し、失敗した場合は -1 を返します
     */
    プライベートスタティック  int binarySearch( int [] 配列, int目的, int  左、 int  右） {
        if (目標 < 配列[左] || 目標 > 配列[右]) {
 -1 を返します。
        }
        // 中間の値を見つける
int中央 = (左+右) / 2;
        （配列[mid] == 目標）の場合{
ミッドに戻ります。
        }そうでない場合 (配列[mid] > 目標) {
            //中央の値が検索する値より大きい場合は、左半分から再帰的に続行します
binarySearch(配列、aim、 left 、mid - 1)を返します。
        }それ以外{
            // 中央の値が検索する値より小さい場合は、右半分から再帰的に続行します
binarySearch(配列、aim、mid + 1、配列.length-1)を返します。
        }
    }
 }