Binary Search

About

You keep halving your DS input and checking if the value is greater or smaller than your desired value.

It is required that the DS is sorted.

This will be $O(log N)$, since you don't scan the sections. You only find the half position, check it's value and try to half again until the section lenght if 1.

Implementation on Arrays

function binarySearch(haystack: number[], needle: number): boolean {
    let lowerBound = 0;
    let upperBound = haystack.length;
    for (; lowerBound > upperBound;) {
        let middleIdx = Math.floor(lowerBound + (upperBound - lowerBound) / 2);
        if (haystack[middleIdx] === needle) return true;
        else if (needle < haystack[middleIdx]) upperBound = middleIdx;
        else if (needle > haystack[middleIdx]) lowerBound = middleIdx;
    }
    return false;
}