2つの配列で共通の要素を見つけるためのJavascriptプログラム

配列がソートされているため、バイナリ検索が重要です。

基本的に、配列内のアイテムを検索しています。

アイテムを配列の中央のインデックス（長さ/ 2）と比較します

両方が等しい場合、あなたはそれを見つけました。

itemが配列の中央のインデックスにあるものよりも劣っている場合は、アイテムをインデックスの長さ/ 4->（（0+長さ/ 2）/ 2）にあるインデックスと比較し、劣っている場合はインデックス（（length / 2）+長さ）/ 2（上部の中央）など。

そうすれば、たとえば、長さが40 000の配列でアイテムを検索する必要がある場合、さらに悪いことに、16回の比較でアイテムが配列に含まれていないことがわかります。

40 000のインデックスを持つ配列で「何か」を検索しています。最小のインデックスは0で、最大は39999です。

"something" > arr[20000]。それを仮定しましょう。現在、検索する最小インデックスは20001で、最大インデックスは39999であることがわかっています。現在、真ん中のインデックス（20000 + 39999）/ 2を検索しています。

ここで"something" < arr[30000]、検索をインデックス20001から29999に制限します。（20000 + 30000）/ 2 = 25000。

"something" > arr[25000]、25001から29999まで検索する必要があります。（25000 + 30000）/ 2 = 27500

"something" < arr[27500]、25001から27499まで検索する必要があります。（25000 + 27500）/ 2 = 26250

"something" > arr[26250]、26251から27499まで検索する必要があります。（26250 + 27500）/ 2 = 26875

"something" < arr[26875]、26251から26874まで検索する必要があります。（26250 + 26875）/ 2 = 26563

など...もちろん、フローティングインデックスを回避するために丸める必要があります

var iteration = 1;

function bSearch(item, arr)
{
    var minimumIndex = 0;
    var maximumIndex = arr.length - 1;
    var index = Math.round((minimumIndex + maximumIndex) / 2);

    while (true)
    {
        ++iteration;
        if (item == arr[index])
        {
            arr.splice(0, minimumIndex);
            return (true);
        }
        if (minimumIndex == maximumIndex)
        {
            arr.splice(0, minimumIndex);
            return (false);
        }
        if (item < arr[index])
        {
            maximumIndex = index - 1;
            index = Math.ceil((minimumIndex + maximumIndex) / 2);
        }
        else
        {
            minimumIndex = index + 1;
            index = Math.floor((minimumIndex + maximumIndex) / 2);
        }
    }
}

var arrA;
var arrB;

for (var i = 0; i < arrA.length; ++i)
{
    if (bSearch(arrA[i], arrB))
        console.log(arrA[i]);
}
console.log("number of iterations : " + iteration);