# 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.**

{% hint style="info" %}
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.
{% endhint %}

#### Implementation on Arrays

```typescript
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;
}
```