Binary Search Visualizer: Step-by-Step Animation & Complexity

Binary Search

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

Input Data

Visualization

Visual representation of the data structure

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
}

Variable State

{
  "arr": "[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]",
  "target": 23,
  "low": 0
}

Binary Search: How It Works

Last updated October 28, 2026

Overview

Binary Search finds a value in a sorted array by repeatedly halving the range that could contain it. It compares the target with the middle element: if they match, the search is over; if the target is larger, the left half (including the middle) can be thrown away; if smaller, the right half can.

Each comparison removes half of the remaining candidates, so even a billion-element array needs at most about 30 comparisons. The price is the precondition: the array must already be sorted, and the algorithm needs random access to jump straight to the middle.

In the default example the target is 23. The first middle is index 4 (value 16), so the search moves right; the next middle is index 7 (value 56), so it moves left; the third probe lands on index 5, which holds 23.

Step by step

Set low = 0 and high = n - 1.
While low <= high, compute mid = floor((low + high) / 2).
If arr[mid] === target, return mid.
If arr[mid] < target, set low = mid + 1; otherwise set high = mid - 1.
If the loop ends, the target is not present; return -1.

Complexity

Case	Cost	Why
Best case	O(1)	The first middle element is the target.
Average case	O(log n)	The range halves on every comparison.
Worst case	O(log n)	At most floor(log2 n) + 1 comparisons.
Extra space	O(1)	Iterative version; the recursive one uses O(log n) stack.

When to use it

Any repeated lookup in sorted, randomly accessible data.
'Binary search on the answer' problems: finding the smallest value that satisfies a monotonic condition, such as the minimum capacity to ship packages in D days.
Finding insertion points, first/last occurrences, and boundaries (lower_bound / upper_bound).

Common mistakes

low < high versus low <= high and mid - 1 versus mid: mixing conventions causes infinite loops or skipped elements. Pick one invariant and stick to it.
(low + high) / 2 overflows in fixed-width integer languages; use low + (high - low) / 2.
Running it on unsorted data gives wrong answers silently rather than failing.

Worked Example: Binary Search Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Binary Search: follow each row, predict the next one, and compare. The run below takes 16 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 2,5,8,12,16,23,38,56,72,91
Target: 23
Result: return value = 5

Step	Line	Array	What happens
1	2	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	target = 23, low = 0
3	4	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 0, high = 9, condition = 0 <= 9
5	6	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 0, high = 9, mid = 4, arr[mid] = 16, target = 23, condition = 16 === 23
6	8	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 0, high = 9, mid = 4, arr[mid] = 16, target = 23, condition = 16 < 23
8	4	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 5, high = 9, condition = 5 <= 9
10	6	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 5, high = 9, mid = 7, arr[mid] = 56, target = 23, condition = 56 === 23
11	8	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 5, high = 9, mid = 7, arr[mid] = 56, target = 23, condition = 56 < 23
13	4	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 5, high = 6, condition = 5 <= 6
15	6	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	low = 5, high = 6, mid = 5, arr[mid] = 23, target = 23, condition = 23 === 23
16	7	[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]	return value = 5

Frequently Asked Questions

About Binary Search

What is Binary Search?

Binary Search is a highly efficient searching algorithm that works on sorted arrays. It operates by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, it narrows the interval to the lower half. Otherwise, it narrows it to the upper half.

What is the main prerequisite for Binary Search?

The single most important prerequisite for Binary Search is that the array or list must be sorted. If the data is not sorted, the algorithm will not work correctly.

What is the time complexity of Binary Search?

The time complexity is O(log n). With each comparison, the algorithm eliminates half of the remaining elements, which makes it extremely fast for large datasets.

What is the space complexity of Binary Search?

The iterative version of Binary Search has a space complexity of O(1) (in-place). The recursive version has a space complexity of O(log n) due to the recursion call stack.

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

The search continues until the search interval is empty (i.e., when the `low` pointer crosses the `high` pointer). At this point, the algorithm terminates and typically returns a special value, like -1 or null, to indicate that the element was not found.

Can Binary Search be used on a linked list?

No, it is not efficient for standard linked lists. Binary Search relies on direct, O(1) random access to the middle element, but in a linked list, finding the middle element takes O(n) time. This negates the O(log n) advantage.

What happens if there are duplicate elements in the array?

A standard Binary Search will find *an* occurrence of the target element, but it doesn't guarantee which one (e.g., the first or the last). Modified versions are needed to find the first or last occurrence of a duplicate element.

Describe the iterative vs. recursive approach.

The iterative approach uses a `while` loop to manage the `low` and `high` pointers, which is generally more space-efficient and avoids potential stack overflow. The recursive approach defines a function that calls itself with the updated `low` or `high` boundaries, which can be more intuitive to read but uses more memory on the stack.

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

Interpolation search is a variation that, instead of always checking the middle element, makes an educated guess about where the target might be, based on its value relative to the start and end values. It can be faster (O(log log n)) for uniformly distributed data but degrades to O(n) for non-uniform data.

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

You would use a linear search if the data is unsorted, as sorting it first would take O(n log n) time, which is slower than a simple O(n) linear scan. Linear search is also preferable for very small arrays where its simplicity and good cache performance might make it faster in practice.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.

Search in Rotated Sorted Array

From: Flipkart

View Question