TerminalTales

Binary Search Visualization: Step-by-Step Animation

Watch binary search execute line-by-line with synchronized code highlighting and array visualization.

Interactive Binary Search Visualizer
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

Array State

2
0
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
Initialize
Starting binary search for target 23 in a sorted array of 10 elements.
target=23
1/13

About This Binary Search Animation

The interactive visualization above demonstrates how binary search works on a sorted array of 10 integers. We are searching for the target value 23. The animation shows the algorithm executing in real-time, with the Python code highlighted line-by-line as each step executes.

Use the example tabs above the animation to explore different scenarios: finding an element, best-case performance (found immediately), and when the target is not in the array.

In the Code Panel on the left, you can see the actual Python implementation of binary search. The currently executing line is highlighted in amber, allowing you to trace exactly what the algorithm is doing at each moment. The line numbers on the left help you follow along with the code structure.

In the Animation Panel on the right, the array is displayed with visual indicators showing the current state of the search. The L marker shows the low pointer, the H marker shows the high pointer, and the M marker shows the current mid position being examined. Elements within the current search range are highlighted in purple, while elements that have been eliminated are grayed out.

What is Binary Search?

Binary search is one of the most fundamental and widely-used algorithms in computer science. It is a divide-and-conquer algorithm that finds the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half, eliminating half of the remaining elements with each comparison.

Unlike linear search, which checks every element one by one (taking O(n) time in the worst case), binary search achieves O(log n) time complexity. This makes it exponentially faster for large datasets. For example, searching through 1 million elements with linear search could require up to 1 million comparisons, while binary search would need at most 20 comparisons.

How Binary Search Works

The algorithm maintains two pointers, low and high, that define the current search range.

  1. Initialization: Set low = 0 and high = n - 1.
  2. Calculate Mid: Find the middle index: mid = low + (high - low) / 2.
  3. Compare: Check the element at arr[mid]:
    • If equal to target: Return mid (Success).
    • If less than target: The target must be in the right half. Move low = mid + 1.
    • If greater than target: The target must be in the left half. Move high = mid - 1.
  4. Repeat: Continue steps 2-3 while low <= high.
  5. Not Found: If the loop finishes without finding the target, return -1.

Time and Space Complexity

Time Complexity
O(log n)

Each comparison eliminates half of the remaining elements. For n elements, at most log2(n) comparisons are needed.

Space Complexity
O(1)

The iterative version uses only a constant amount of extra space (low, high, mid variables).

When to Use Binary Search

Binary search is applicable in many scenarios beyond simple element lookup. Here are the key conditions and common use cases:

  • The data must be sorted (or have a monotonic property)
  • Finding a specific element or determining if it exists
  • Finding the insertion point for a new element
  • Finding the first or last occurrence of a duplicate element
  • Searching in rotated sorted arrays
  • Finding the square root or nth root of a number
  • Searching for a peak element in an array
  • Binary search on the answer (optimization problems)

Common Mistakes and How to Avoid Them

Binary search has a reputation for being tricky to implement correctly. Here are the most common pitfalls:

  • Integer overflow: The expression (low + high) / 2 can overflow in languages with fixed-size integers when low and high are both large. Always use low + (high - low) / 2 instead.
  • Off-by-one errors: Be careful when updating the pointers. Using low = mid instead of low = mid + 1 can cause infinite loops. Always ensure the search space shrinks with each iteration.
  • Incorrect loop condition: Use while low <= high for standard binary search. Using < instead of <= can cause you to miss the target when it is the last remaining element.
  • Forgetting the sorted requirement: Binary search only works on sorted data. If your input is not sorted, you must sort it first (adding O(n log n) time) or use a different algorithm.

Binary Search Variations

The basic binary search template can be adapted to solve many different problems:

Lower Bound (First Occurrence)

Find the first index where the target appears. When arr[mid] == target, continue searching left.

Upper Bound (Last Occurrence)

Find the last index where the target appears. When arr[mid] == target, continue searching right.

Rotated Array Search

Search in a sorted array that has been rotated. Determine which half is sorted before deciding where to search.

Master Binary Search with TerminalTales

Binary Search is one of the top 5 most common patterns in technical interviews. To truly master it (and its tricky variations like finding the lower/upper bound), you need more than just a blog post.

TerminalTales is a story-driven DSA course that gives you deep, structured practice on Binary Searchand other essential patterns. We help you build the intuition to know exactly when to apply it so you don't blank out during your interview.

What You Will Learn

  • Pattern recognition: instantly identify when to use binary search
  • Key variations: lower bound, upper bound, and more
  • Common interview problems with step-by-step solutions
  • Spaced repetition reviews to lock in your knowledge permanently

Start with 3 free chapters and experience the difference that story-driven learning makes. Join thousands of engineers who have used TerminalTales to land their dream jobs at top tech companies.

Related Algorithms

Linear SearchAll Visualizations

Master DSA with Story-Driven Learning

TerminalTales combines an immersive narrative with spaced repetition to help you actually remember what you learn.

Start Learning Free
All Visualizations
TerminalTales - Story-Driven DSA Interview Prep That Actually Sticks