Back

Binary Search Algorithm

Interactive Demonstration

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half.

Enter a number and click 'Search' or 'New Array' to begin.

How Binary Search Works

Binary search follows these steps:

  1. Start with the middle element of the sorted array.
  2. If the target value is equal to the middle element, we've found it!
  3. If the target value is less than the middle element, search the left half.
  4. If the target value is greater than the middle element, search the right half.
  5. Repeat steps 1-4 until the element is found or the search space is empty.

Time and Space Complexity

Time Complexity

O(log n) - With each step, we eliminate half of the remaining elements.

Space Complexity

O(1) - Iterative approach uses constant extra space.

Implementation

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        let guess = arr[mid];
        
        if (guess === target) {
            return mid; // Found the item
        }
        if (guess > target) {
            high = mid - 1; // Target is in the left half
        } else {
            low = mid + 1; // Target is in the right half
        }
    }
    
    return -1; // Item not found
}