検索アルゴリズム--データ構造とアルゴリズムのjavascript記述第13章

検索アルゴリズム-どのようにリストで特定の値を検索しますか?
逐次検索
リストの最初の要素からリスト要素を一つずつ判断し、所望の結果が見つかるまでは、暴力検索のテクニックの一種であり、検索を実行する時はデータ構造のすべての要素にアクセスすることがあります.
コード:

//  1
function seqSearch1(arr,data){
    //    
    //               
    //v1      
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            return true;
        }
    }
    return false;
}

//            -1
function seqSearch2(arr,data){
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            return i;
        }
    }
    return -1;
}

最大値と最小値を検索

function findMin(arr){
    var min = arr[0]
    for(var i=0;i<arr.length;++i){
        min = Math.min(arr[i],min)
    }
    return min;
}
function findMax(arr){
    var min = arr[0]
    for(var i=0;i<arr.length;++i){
        min = Math.max(arr[i],min)
    }
    return min;
}

並べ替えなしの検索
並べ替えられていないデータセットの場合、検索されたデータがデータセットの開始位置にあるとき、検索は最も速く、最も成功します.
問題点:
データが並べ替えられていない場合、データを探すには多くの時間がかかります.並べ替えられていないデータセットの場合、検索されたデータがデータセットの開始位置にあるとき、検索は最も速く、最も成功します.このアイデアは82理論と参照してください.80%の検索は20%のデータを探しています.私たちは検索された要素をデータの開始位置に配置して、配列の並べ替えを変えます.この方法を使うと、最も頻繁な要素を探して最終的にはデータセットの開始位置に移動します.
コード:

function seqSearch3(arr,data){
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            if (i > 0) {
                //      。
                swap(arr,i,i-1);
            }
            return true;
        }
    }
    return false;
}
function swap(arr, index, index1) {
    var temp = arr[index];
    arr[index] = arr[index1];
    arr[index1] = temp;
}

このバージョンは連続して数劇の位置を修正しますが、問題があります.データは前の位置にありますが、前に置かれることもあります.この元素は20%の位置にあるかどうかを判断します.位置があれば、位置を変えません.
アップグレード:

function seqSearch4(arr,data){
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data && i > (arr.length * 0.2)) {
            swap(arr,i,0);
            return true;
        }
        else if (arr[i] == data) {
            return true;
        }
    }
    return false;
 
}

二分割検索
二分割検索は、秩序データに基づいている.順序検索よりも効率が高いです.
基本的な考え方:
一つの数字を当て始めて、データの中間の値と検索値を比較します.3つの状況があります.当てが大きくなったり、当てが小さくなったりすると、繰り返してデータを処理して中間値を探し直してから判断します.
コード:

function binSearch(arr,data){
    var topBound = arr.length-1;
    var bottomBound = 0;
    while(bottomBound<=topBound){
        var mid = Math.floor((topBound + bottomBound) / 2);
        if (arr[mid] < data) {
            bottomBound = mid + 1;
        }
        else if (arr[mid] > data) {
            topBound = mid - 1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

以上は私達の二分検索方式ですが、規則的なデータの中に同じ値が複数あると、どうやっていくつかの種類があるか分かりますか?
統計方法を追加:

//       34         34，34，34   2          ，           3 34
//                       
function binCount(arr,data){
    var count = 0;
    var pos = binSearch(arr,data)
    if(pos>-1){
        ++count;
        for(var i=pos-1;i>0;--i){
            if(arr[i]==data){
                ++count;
            }else{
                break;
            }
        }
        for(var i=pos+1;i<arr.length;++i){
            if(arr[i]==data){
                ++count;
            }else{
                break;
            }
        }
    }
    return count;
}

テスト:

//       
function createArr(){
    var nums = [];
    for (var i = 0; i < 100; ++i) {
        nums[i] = Math.floor(Math.random() * 101);
    }
    return nums;
}
var nums = createArr();
 
 //          
nums.sort(function(n1,n2){
    return n1-n2;
})
var n=46
console.log("  ："+ binCount(nums,46)+"      ")