javascript - 如何使用二进制搜索比较 Javascript 中的两个数组？

Question

我如何使用二进制搜索来比较两个数组并计算它匹配的次数，我确实在这里找到了一些将一个项目与一个数组进行比较的地方..follwing 是常规的，例如..thanx 的帮助。

var a = ["1", "2", "3", "4", "5", "6", "7"];
var b = ["8", "1", "3", "9", "4", "6", "8"];
var count = 0;

for (i = 0; i < a.length; i++) {
    for (j = 0; j < b.length; j++) {
        if (a[i] == b[j]) count += 1;
    }
}

document.write(count);

我试着这样做..

for (i = 0; i < a.length; i++) {
    var left = 0;
    var right = b.length - 1;
    while (left <= right) {
        var mid = parseInt((left + right) / 2);
        if (b[mid] == a[i]) {
            count += 1;
        } else if (b[mid] < a[i]) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
}

document.write(count);

Answer 1

线性遍历b数组并使用数组的二进制搜索a。

function binarySearch(a, value) {
    var left = 0;
    var right = a.length - 1;
    while (left <= right) {
        var mid = (left + right) >> 1;
        if (a[mid] === value) {
            return mid;
        } else if (a[mid] < value) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}


var a = ["1", "2", "3", "4", "5", "6", "7"];
var b = ["8", "1", "3", "9", "4", "6", "8"];
var count = 0;
b.forEach(function(value) { if (binarySearch(a, value) >= 0) ++count; });