AlgoViz: Interactive Algorithm Visualization Tool

Binary Search

Category: Searching | Time: O(log n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Binary Search

An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

Code Editor

The code is for reference. Editing it won't affect the visualization.

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

Frequently Asked Questions

About Binary Search

What is Binary Search?

What is the main prerequisite for Binary Search?

What is the time complexity of Binary Search?

What is the space complexity of Binary Search?

How does Binary Search handle an element that is not in the array?

Can Binary Search be used on a linked list?

What happens if there are duplicate elements in the array?

Describe the iterative vs. recursive approach.

What is an 'interpolation search' and how does it compare?

When would you prefer a linear search over a binary search?

Where can I learn more?