binary-search.js

/**
 * Searches for a target value in a sorted array using binary search.
 *
 * Time Complexity: O(log n) in all cases.
 * Space Complexity: O(1).
 *
 * Use when: Searching in sorted arrays repeatedly.
 * Avoid when: Array is unsorted (use linear search) or only one search (linear may be simpler).
 * Requirement: Array MUST be sorted.
 */
const binarySearch = (arr, target) => {
    let low = 0, high = arr.length;

    let middle;

    while (low < high) {
        middle = Math.floor((low + high) / 2);

        if (arr[middle] === target) {
            return middle;
        }

        arr[middle] < target ? low = middle : high = middle;
    }

    return -1;
}

const sortedArray = [4, 8, 15, 16, 23, 42];

console.log("Not found: ", binarySearch(sortedArray, 3));
console.log("Found at index: ", binarySearch(sortedArray, 23));
console.log("Found at index: ", binarySearch(sortedArray, 8));