Бинарный поиск против перебора (тупого поиска) (v4)

Revision 4 of this benchmark created on

Setup

const arr = new Array(1000000)

for (let i=0; i < arr.length; i++) {
	arr[i] = i + 1;
}

Test runner

Ready to run.

Testing in
TestOps/sec
Рекурсивный бинарный поиск
var  searchRec = function (nums, target) {
    let left = -1;
    let right = nums.length;

    let binarySearch = (nums, target, left, right) => {
        const mid = Math.floor((right + left) / 2);

        if (target === nums[mid]) {
            return mid;
        } else if (right === left) {
            return -1
        }

        if (target < nums[mid]) {
            return binarySearch(nums, target, left, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, right);
        }
    };

    return binarySearch(nums, target, left, right);
}

console.log(searchRec([1, 3, 5, 6], 3));
ready
Бинарный поиск
function searchInsert(nums, target) {
    let left = -1;
    let right = nums.length;

    while (right - left > 1) {
        let mid = Math.floor((right + left) / 2);

        if (target == nums[mid]) {
            return mid;
        }

        if (target > nums[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

console.log(searchInsert([1, 3, 5, 6], 3));
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.