JAvascriptデータ構造とアルゴリズム-検索アルゴリズム

前言
本書では、2つの検索アルゴリズムについて説明していますが、紙面は大きくありません.これまでの知識点が融合しているので、比較的簡単に見えます.主に2つの内容が含まれています.

シーケンス検索

二分探索

シーヶンスサーチ
  字面の意味から见ると、见つかるまで顺番に一つ一つ探していくという意味です.検索の結果はtrue、現在のインデックス、現在の値を返すことができます.そうしないとfalse、-1、nullなどの内容を返します.次のコードを参照してください.

    var sequentialSearch = function(item){
        for (var i = 0;i

全体的な考え方は、データを遍歴し、遍歴した各コンテンツを、私たちが検索する要素と比較して、値が等しい場合は遍歴を終了し、returnを使用して返します.そうしないと、遍歴が終了したときに他のコンテンツを返します.値が3の要素アイテムを検索する配列があるとします.

[5,4,3,2,1]

検索の概略図は次のとおりです.
にぶんたんさく
  いわゆる二分とは、データを二分し、まず中間値を選択し、中間値が検索する必要がある場合は、その値を返します.そうしないと、検索する必要がある値をこの中間値と比較し、検索するまで順番にこのステップを繰り返します.

                      。

配列の中間値

を選択する.

中間値が探索対象値である場合、アルゴリズム実行は

を終了する.

検索対象の値が中間値より小さい場合は、最初のステップに戻り、選択値の左側に

を検索する.

検索対象の値が中間値より大きい場合は、2番目のステップに戻り、選択値の右側に

を検索する.
コード実装:

    let binarySearch = function(item){
        //        
        quickSort(array);
        
        let low = 0,
            hight = array.length - 1,
            mid,element;
        
        while (low <= high){
            mid = Math.floor((low + high) / 2);
            element = array[mid];
            if(element < item){
                low = mid + 1;
            }else if(element>item){
                high = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

アルゴリズムが実行するステップの例を示します.
ここの内容の大部分は本の中で抜粋した内容で、途中で急速なソートについて話しました.他の資料を調べて理解することができます.ソートアルゴリズムに関する内容は、JSでよく見られるソートアルゴリズムが主にあります.もちろん、ここでは他のソート方法を使用することもできます.例えば、泡のソート、選択ソート、挿入ソート、集計ソートなどです.