Binary search finds a target in a sorted array/list by comparing with the middle element and discarding half of the range each step. It requires sorted input and runs in O(log n) time (iteratively using O(1) extra space).
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}