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

[[396063]]

基本的な紹介

1. バイナリ検索は、順序付けられたシリーズ（数字や文字など）の検索にのみ適用できます。検索する前にシリーズを並べ替えてください。

2. バイナリ検索法の実行時間は対数時間 O(log2n) です。つまり、必要なターゲット位置を見つけるのに最大で log2n ステップしかかかりません。ターゲット番号 30 がキュー [0,99] から見つかったと仮定すると、必要な検索ステップ数は log2(100) です。つまり、最大で 7 回かかります (2^6<100<2^7)。

コード例

パッケージ com.xie.algorithm; 
 
パブリッククラス BinarySearchNoRecur {
公共 静的void main(String[] args) {
 int [] arr = {1, 3, 8, 10, 11, 67, 100};
整数 インデックス= binarySearch(arr, 1);
        システム.out.println ( "index = " + index );
    } 
 
    /**
     * 二分探索の非再帰実装
     *
     * @param arr 検索する配列。arrは昇順です
     * @param target 検索する番号
     * @returnは対応するインデックスを返します。-1は見つからないことを意味します。
     */
公共 静的  intバイナリサーチ( int [] arr, intターゲット) {
整数 左= 0;
整数 右= arr.length - 1;
        （左<=右）{
 int中央 = (左+右) / 2;
            （arr[mid] == ターゲット）の場合{
ミッドに戻ります。
            }そうでなければ(arr[mid] > target) {
                //左に検索する必要がある
右= 中央 - 1; 
 
            }それ以外{
                // 右方向に検索する必要があります。
左= 中央 + 1;
            }
        }
 -1 を返します。
    }
 }

基本的な紹介

1. 補間検索アルゴリズムはバイナリ検索に似ていますが、補間検索が毎回適応中間点から開始される点が異なります。

2. バイナリ検索で中間インデックスを見つけるための式は、補間検索中間インデックス式に変換されます。ここで、low は左側のインデックスを表し、high は右側のインデックスを表し、key は検索する値を表します。

コード例

パッケージ com.xie.search; 
 
 java.util.ArrayList をインポートします。
 java.util.List をインポートします。 
 
パブリッククラス InsertValueSearch {
静的 整数 カウント= 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 = insertValueSearch(arr, 0, arr.length - 1, 1);
        システム.out.println ( "indexList = " + indexList);
        System.out.println ( "検索数:" + count ); 
 
        /*
        インデックスリスト = [1, 0]
        検索数: 1
         */
    } 
 
    /**
     * 補間検索、インデックスコレクションを返す
     *
     * @param arr 配列
     * @param left左インデックス
     * @param right右インデックス
     * @param findValue 検索する値
     * @return見つかった場合はすべてのインデックスのコレクションを返し、見つからない場合は空を返します
     */
公共 静的リスト<整数> insertValueSearch( int [] arr, int  左、 int  右、 int findValue) {
カウント++;
        リスト<整数> indexList = 新しい ArrayList<整数>();
        //注意: findValue < arr[0] || findValue > arr[arr.length - 1] が必要です。そうでない場合、mid が範囲外になる可能性があります。
        if (左>右|| findValue < arr[0] || findValue > arr[arr.length - 1]) {
新しいArrayList<Integer> ( )を返します。
        }
 int mid = left + ( right - left ) * (findValue - arr[ left ]) / (arr[ right ] - arr[ left ]);
 int midValue = arr[mid]; 
 
        （findValue > midValue）の場合{
 insertValueSearch(arr, mid + 1, right , findValue)を返します。
        }そうでない場合 (findValue < midValue) {
 insertValueSearch(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を返します。
        }
    }
 }