prep4place
Back to Visualizer

Binary Search

Binary Search efficiently finds elements in a sorted array by repeatedly dividing the search interval in half. It's one of the most important algorithms in computer science.

O(log n)Requires Sorted Array
Size:20
Speed:
Search Range
Middle Element
Eliminated
Found
0
Comparisons Made
5
Max Comparisons (log₂n)

How It Works

  1. 1Array must be sorted for binary search
  2. 2Find the middle element of current range
  3. 3Compare middle element with target
  4. 4If equal, target found!
  5. 5If target is larger, search right half
  6. 6If target is smaller, search left half
  7. 7Repeat until found or range is empty

Why O(log n)?

Each comparison eliminates half of the remaining elements. For an array of 1 million elements, binary search needs at most 20 comparisonsvs. 1 million for linear search!

Time Complexity

Best CaseO(1)
Average CaseO(log n)
Worst CaseO(log n)
Space ComplexityO(1)

Code

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid; // Found!
    } else if (arr[mid] < target) {
      left = mid + 1; // Search right half
    } else {
      right = mid - 1; // Search left half
    }
  }
  
  return -1; // Not found
}