0

二分探索を使用して2つの配列を比較し、一致した回数をカウントするにはどうすればよいですか。ここで、1つの項目が配列と比較されたものを見つけました。

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);
4

1 に答える 1

0

配列を直線的に調べ、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; });
于 2013-01-17T21:42:08.733 に答える