Binary Search

sorteddivide-and-conquerefficient

Press play to start

1function binarySearch(arr: number[], target: number): number {
let low = 0, high = arr.length - 1;
while (low <= high) {
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) low = mid + 1;
  else high = mid - 1;
}
return -1;
10}

Step 1/0

Custom array:

Complexity

Best:O(1)
Average:O(log n)
Worst:O(log n)
Space:O(1)

Description

On a sorted array, repeatedly halves the search space by comparing the target with the middle element.

When to use

O(log n) search for sorted arrays. Use when the data is sorted and searches are frequent (libraries, databases, competitive programming).