javascript - 要素がソートされた配列にあるかどうかを判断する最速の方法

Question

1,000 以上の値 (最大 5000 以上) を持つソートされた int の配列があります。int を受け取り、配列内の要素に基づいて bool を返す関数を作成する必要があります。ブレーク付きの for ループを記述できることはわかっています。jquery .InArray を使用できることもわかっています。

配列がソートされていることを知って、これを実装する最良の方法は何でしょうか。

ありがとう。

Answer 1

二分探索ルーチンを使用したいと思います。二分探索ルーチンは、線形探索は平均してです。

フォームを選択するための多くのバリエーションがあります。これが私がこの記事で見つけたものです：

function binarySearch(items, value){

    var startIndex  = 0,
        stopIndex   = items.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);

    while(items[middle] != value && startIndex < stopIndex){

        //adjust search area
        if (value < items[middle]){
            stopIndex = middle - 1;
        } else if (value > items[middle]){
            startIndex = middle + 1;
        }

        //recalculate middle
        middle = Math.floor((stopIndex + startIndex)/2);
    }

    //make sure it's the right value
    return (items[middle] != value) ? -1 : middle;
}

または、無数の異なる言語でのバイナリ検索機能を備えた、この記事のこのよりシンプルなバージョン。

function binary_search_iterative(a, value) {
    var lo = 0, hi = a.length - 1, mid;
    while (lo <= hi) {
        mid = Math.floor((lo+hi)/2);
        if (a[mid] > value)
            hi = mid - 1;
        else if (a[mid] < value)
            lo = mid + 1;
        else
            return mid;
    }
    return null;
}

ここにコードを使用したGoogleクロージャーのバイナリ検索もあります。

そして、ウィキペディアで二分探索アルゴリズムがどのように機能するかについての良い説明。

Answer 2

配列がソートされていることを知っていれば、二分探索が最善の方法です。

Answer 3

配列がソートされている場合、答えはソートされています - バイナリチョップを使用してください。

Answer 4

多くの言語ですでにこれが実装されています。たとえば、Javaでは、CollectionsCollections.binarySearch（List> list、T key）メソッドを使用できます。また、C＃にも何らかのBinarySearchメソッドがあると確信しています。