Java プログラミングスキル - データ構造とアルゴリズム「バイナリ検索」

[[395207]]

必要

順序付けられた配列 {1,8,10,89,1000,1234} に対してバイナリ検索を実行し、数値を入力して配列内に存在するかどうかを確認し、添え字を見つけます。存在しない場合は、「そのようなデータはありません」というメッセージが表示されます。

思考分析

まず、配列の中央の添え字 mid=(left+right)/2 を決定します。
次に、検索する数値 findValue を arr[mid] と比較します。findValue > arr[mid] の場合、検索する数値は arr[mid] の右側にあるため、右に再帰します。findValue < arr[mid] の場合、検索する数値は arr[mid] の左側にあるため、左に再帰します。findValue == arr[mid] の場合、数値が見つかったため、戻ります。
再帰を終了する条件が見つかったときに再帰は終了します。配列全体を再帰してもfindValueが見つからない場合は、再帰を終了する必要があります。つまり、left > rightのときです。

コード例

パッケージ com.xie.search; 
 
 java.util.ArrayList をインポートします。
 java.util.Arrays をインポートします。
 java.util.List をインポートします。 
 
パブリッククラスBinarySearch {
静的 整数 カウント= 0; 
 
公共 静的void main(String[] args) {
 int [] arr = 新しいint [102];
        ar[0] = 1;
        ar[1] = 1;
 ( int i = 2; i < 102; i++) {
            arr[i] = i;
        }
        リスト<整数> indexList = binarySearch(arr, 0, arr.length - 1, 1);
        システム.out.println ( "indexList = " + indexList);
        System.out.println ( "検索数:" + count );
        /*
        インデックスリスト = [1, 0]
        検索数: 6
         */
    } 
 
    /**
     * バイナリ検索、値に一致するすべてのインデックスセットを検索
     *
     * @param arr 配列
     * @param left左インデックス
     * @param right右インデックス
     * @param findValue 検索する値
     * @return見つかった場合はすべてのインデックスのコレクションを返し、見つからない場合は空を返します
     */
公共 静的リスト<整数> バイナリ検索( int [] arr, int  左、 int  右、 int findValue) {
カウント++;
        リスト<整数> indexList = 新しい ArrayList<整数>();
        // left > rightの場合、再帰は完了します
        （左＞右）の場合{
新しいArrayList<Integer> ( )を返します。
        }
 int中央 = (左+右) / 2;
 int midVal = arr[mid];
        （findValue > midVal）の場合{
            // 見つける値は中央の値よりも大きく、右に再帰的に
binarySearch(arr, mid + 1, right , findValue)を返します。
        }そうでない場合 (findValue < midVal) {
            // 見つける値は中央の値より小さいので、左に再帰的に
binarySearch(arr, left , mid - 1, findValue)を返します。
        }それ以外{
            //見つかった場合は左にスキャンし、条件を満たすものをindexListに追加します
整数 温度= 中間 - 1;
            （真）の間{
                if ( temp < 0 || arr[ temp ] != findValue) {
                    壊す;
                }
                indexList.add ( temp ) ;
温度--;  
            } 
 
            // 再び右にスキャンし、条件を満たすものをindexListに追加します
温度= 中間 + 1;
            （真）の間{
                if ( temp > right || arr[ temp ] != findValue) {
                    壊す;
                }
                indexList.add ( temp ) ;
一時++;
            }
            インデックスリストを追加します(mid);
 indexListを返します。
        }
    }
 }