💾 Archived View for disconnect.wiki › algorithms › binary-search.gmi captured on 2023-05-24 at 17:41:23. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Binary Search

Video Reference

Video about the problem on youtube

Introduction

Problem :: Given an array `[2,3,5,6,8,10,12]`, find the index target value `10`.

The idea for the binary search is to reduce the number of operations to find an element on a given set, either lexicograph or numerically, as long as the set is ordered. It does it by getting the middle element of the list, search to the left if the middle is bigger than the one we need, and right if the element is smaller.

So, for the given example, we follow these steps:

First we get the middle element of the set, compare it with the target.

Set :: `[2,3,5,6,8,10,12]`
Left, Right :: `0, 6`
Middle :: `6`

The middle is smaller than the target, so we move left to middle + 1 and repeat.

Set :: `[8,10,12]`
Left, Right :: `4, 6`
Middle :: `10`

The middle is now precisely 10, so we return.

If we were instead looking for a number that is not on the set, say `13`:

We continue from step 2, before we found the element:

Set :: `[8,10,12]`
Left, Right :: `4, 6`
Middle :: `10`

The middle is smaller than the target, so we move left again:

Set :: `[12]`
Left, Right :: `5, 6`
Middle :: `12`

The middle is smaller than the target, so we move left again, and `left == right`, so we return:

Set :: `[]`
Left, Right :: `6, 6`

Algorithm implementation

Complexity :: O(log(n))

const binarySearch = (input, target) => {
    let [left, right] = [0, input.length - 1];

    while (left <= right) {
        const mid = left + Math.ceil((right - left) / 2);
        console.log(`Set :: ${input.slice(left,right)}`);
        console.log(`Left, Right :: ${left}, ${right}`);
        console.log(`Mid :: ${mid}`);

        if (input[mid] == target) {
            console.log(`Found :: ${input[mid]} (index ${mid})`);
            return mid;
        }

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

    console.log("Not Found");
    return -1;
};

const input = [1,2,3,4,5];
const assert = require('assert');
assert.equal(binarySearch(input, 2), 1);
console.log();
assert.equal(binarySearch(input, 4), 3);
console.log();
assert.equal(binarySearch(input, 5), 4);
console.log();
assert.equal(binarySearch(input, 12), -1);
console.log();

Results in:

Set :: 1,2,3,4
Left, Right :: 0, 4
Mid :: 2
Set :: 1
Left, Right :: 0, 1
Mid :: 1
Found :: 2 (index 1)

Set :: 1,2,3,4
Left, Right :: 0, 4
Mid :: 2
Set :: 4
Left, Right :: 3, 4
Mid :: 4
Set ::
Left, Right :: 3, 3
Mid :: 3
Found :: 4 (index 3)

Set :: 1,2,3,4
Left, Right :: 0, 4
Mid :: 2
Set :: 4
Left, Right :: 3, 4
Mid :: 4
Found :: 5 (index 4)

Set :: 1,2,3,4
Left, Right :: 0, 4
Mid :: 2
Set :: 4
Left, Right :: 3, 4
Mid :: 4
Not Found

Implementation Details

Mid point calculation

The popular algorithm that you can find for binary search usually does something like this:

const [left, right] = [ 0, 3 ];
return Math.ceil((left + right) / 2);

For many languages this is ok-ish, because numbers move between number types seamlessly. That's not the case with Rust or C++, where number types have fixed sizes. In this case, summing `left` and `right` can overflow, breaking the algorithm completely.

The correct solution for this bug is something like this:

const [left, right] = [ 0, 3 ];
return left + Math.ceil((right - left) / 2);

That way the numbers will not overflow, as long as the number type for `mid`, `left` and `right` are the same.

Probably faster, but not as clear is:

const [left, right] = [ 0, 4 ];
return (left + right) >>> 1;

This is a real world problem that happens on real projects, like on the JVM:

Java's Binary Search Madness

Problems

Find first value bigger or equal to x

The main difference is that we do not return if the value immediately found. Instead, we continue looking for a smaller element, moving left if it is bigger, and right if it is smaller.

const binarySearch = (input, target) => {
    let [left, right] = [0, input.length - 1];
    let answer = -1;

    while (left <= right) {
        const mid = left + right >>> 1;

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

    return answer;
};

const input = [1, 3, 5, 7];
const assert = require('assert');
assert.equal(binarySearch(input, 2), 1);
assert.equal(binarySearch(input, 4), 2);
assert.equal(binarySearch(input, 5), 2);
assert.equal(binarySearch(input, 12), -1);