Binary Search

An efficient algorithm for finding a target value in a sorted array by repeatedly dividing the search interval in half.

Binary Search Visualization

range: [–, –]
SlowFast
🔊 Sound
ReadyGenerate an array and enter a target value to search.
MidActive rangeFoundEliminated↓ low↑ mid↓ high

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Pseudocode

function binarySearch(arr, target):
  left = 0
  right = length(arr) - 1
  while left <= right:
    mid = floor((left + right) / 2)
    if arr[mid] == target:
      return mid
    else if arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1