Binary search is frequently praised as one of the most efficient algorithms for finding an element in a sorted dataset. It’s fast—blazingly fast—and its efficiency grows more apparent as the size of the search space increases. But how can we truly appreciate its speed in a world where computers perform millions of operations per second?

Let’s flip the script: we’re going to intentionally slow down the algorithm by adding a one-second delay to each iteration. This simple twist will help us feel the power of binary search and understand how its logarithmic efficiency scales with the size of the dataset.

Before diving into the code, let’s quickly recap binary search. Given a sorted list, binary search divides the list in half at each step, checking whether the target value lies in the left or right half. This process continues until the target is found or the search space is reduced to zero.

Here’s why it’s so efficient: with each step, the size of the search space is halved. For example:

  • A list of 1,000 elements requires at most 10 comparisons.
  • A list of 1 million elements? Just 20 comparisons.
  • A list of 1 billion elements? 30 comparisons.

The twist: slowing it down

To make the efficiency of binary search tangible, we’ll modify the algorithm by adding a one-second delay to each iteration. This way, the time taken will scale directly with the number of steps the algorithm performs. Watching the algorithm process datasets of different sizes will give us an intuitive understanding of how it scales.

Here’s the implementation:

import time
import sys

def binary_search(arr, target):
    """Performs a binary search with a 1-second delay per iteration."""
    low, high = 0, len(arr) - 1
    iterations = 0  # Track the number of iterations

    while low <= high:
        iterations += 1
        mid = (low + high) // 2
        print(f"Iteration {iterations}: Checking index {mid} (value: {arr[mid]})")

        # Artificial delay to simulate time passing
        time.sleep(1)

        if arr[mid] == target:
            print(f"Found {target} at index {mid} after {iterations} seconds.")
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    print(f"{target} not found after {iterations} seconds.")
    return -1

if __name__ == "__main__":
    # Parse command-line arguments
    if len(sys.argv) != 3:
        print("Usage: python binary_search.py <array_size> <target_value>")
        sys.exit(1)

    try:
        array_size = int(sys.argv[1])
        target = int(sys.argv[2])
    except ValueError:
        print("Both array_size and target_value must be integers.")
        sys.exit(1)

    # Generate the sorted array
    array = list(range(array_size))

    print(f"Starting binary search for {target} in an array of size {array_size}...\n")
    # Run the binary search
    binary_search(array, target)

How to run the script

python binary_search.py <array_size> <target_value>

Examples

10 elements

% python3 script.py 10 4
Starting binary search for 4 in an array of size 10...

Iteration 1: Checking index 4 (value: 4)
Found 4 at index 4 after 1 seconds.

1000 elements

% python3 script.py 1000 572
Starting binary search for 572 in an array of size 1000...

Iteration 1: Checking index 499 (value: 499)
Iteration 2: Checking index 749 (value: 749)
Iteration 3: Checking index 624 (value: 624)
Iteration 4: Checking index 561 (value: 561)
Iteration 5: Checking index 592 (value: 592)
Iteration 6: Checking index 576 (value: 576)
Iteration 7: Checking index 568 (value: 568)
Iteration 8: Checking index 572 (value: 572)
Found 572 at index 572 after 8 seconds.

1 million elements

% python3 script.py 1000000 78246
Starting binary search for 78246 in an array of size 1000000...

Iteration 1: Checking index 499999 (value: 499999)
Iteration 2: Checking index 249999 (value: 249999)
Iteration 3: Checking index 124999 (value: 124999)
Iteration 4: Checking index 62499 (value: 62499)
Iteration 5: Checking index 93749 (value: 93749)
Iteration 6: Checking index 78124 (value: 78124)
Iteration 7: Checking index 85936 (value: 85936)
Iteration 8: Checking index 82030 (value: 82030)
Iteration 9: Checking index 80077 (value: 80077)
Iteration 10: Checking index 79100 (value: 79100)
Iteration 11: Checking index 78612 (value: 78612)
Iteration 12: Checking index 78368 (value: 78368)
Iteration 13: Checking index 78246 (value: 78246)
Found 78246 at index 78246 after 13 seconds.

1 billion elements

% python3 script.py 1000000000 708246
Starting binary search for 708246 in an array of size 1000000000...

Iteration 1: Checking index 499999999 (value: 499999999)
Iteration 2: Checking index 249999999 (value: 249999999)
Iteration 3: Checking index 124999999 (value: 124999999)
Iteration 4: Checking index 62499999 (value: 62499999)
Iteration 5: Checking index 31249999 (value: 31249999)
Iteration 6: Checking index 15624999 (value: 15624999)
Iteration 7: Checking index 7812499 (value: 7812499)
...
Iteration 25: Checking index 708248 (value: 708248)
Iteration 26: Checking index 708233 (value: 708233)
Iteration 27: Checking index 708240 (value: 708240)
Iteration 28: Checking index 708244 (value: 708244)
Iteration 29: Checking index 708246 (value: 708246)
Found 708246 at index 708246 after 29 seconds.

Why this matters

This experiment (hopefully) demonstrates the elegance of binary search. By slowing it down, we make its logarithmic behavior easy to observe and appreciate. No matter how large the dataset, the number of steps grows at a manageable rate.

Try It Yourself

Run the code, tweak the dataset sizes, and experiment with different target values. If you’re teaching others about algorithms or learning them yourself, this slowed-down version of binary search might be a good way to to give them a "feel" for it.

What are your thoughts on this approach? Do you have any other creative twists for understanding algorithms? Share your ideas in the comments below!

Author Of article : Arik Read full article