Binary Search Algorithm Overview

👋 Welcome Gophers! In this lesson, we are going to be covering the Binary Search algorithm and why it’s so incredibly efficient.

Overview

After exploring graph traversal, let’s shift gears and look at searching in sorted data. Binary Search is one of the most elegant and efficient algorithms out there.

The key requirement: your data must be sorted. But when it is, Binary Search is lightning fast. Instead of checking every element (linear search), we eliminate half the search space with each comparison. That’s the power of divide-and-conquer!

How It Works

Binary Search works by repeatedly dividing the search space in half:

Start with a sorted array
Find the middle element
If it’s your target, you’re done!
If the target is less than the middle, search the left half
If the target is greater than the middle, search the right half
Repeat until found or search space is empty

It’s like searching a phone book—you don’t start at page 1. You open to the middle, see if you’re too early or too late, then narrow your search accordingly.

Why It’s Fast

With a 1 million element array:

Linear search: Up to 1,000,000 comparisons
Binary search: Maximum 20 comparisons!

This is because we’re halving the search space each time. After k steps, we’ve searched 2^k elements. So to search 2^20 (about 1 million) elements, we need at most 20 steps. That’s O(log n) complexity!

Key Properties

Requires sorted data: Without sorting, binary search won’t work
Divide-and-conquer: We split the problem in half each time
Best and worst case: Always O(log n) once data is sorted
Iterative and recursive: Both implementations work great

Time and Space Complexity

Time Complexity: O(log n) where n is the number of elements
Space Complexity: O(1) for iterative, O(log n) for recursive (call stack)

Visual Example

Let’s see Binary Search narrowing down the search space:

<svg viewBox="0 0 700 380" xmlns="http://www.w3.org/2000/svg">
  <!-- Background -->
  <rect width="700" height="380" fill="#1a1a2e"/>

  <!-- Title -->
  <text x="350" y="30" text-anchor="middle" fill="#00d9ff" font-size="18" font-weight="bold">
    Binary Search: Finding Target Value 42
  </text>

  <!-- Step 1: Full Array -->
  <text x="50" y="70" fill="#888" font-size="11" font-weight="bold">Step 1: Check Middle</text>

  <rect x="50" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="65" y="104" text-anchor="middle" fill="#fff" font-size="10">5</text>

  <rect x="85" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="100" y="104" text-anchor="middle" fill="#fff" font-size="10">12</text>

  <rect x="120" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="135" y="104" text-anchor="middle" fill="#fff" font-size="10">18</text>

  <rect x="155" y="85" width="30" height="25" fill="#ff6b6b" stroke="#00d9ff" stroke-width="2"/>
  <text x="170" y="104" text-anchor="middle" fill="#fff" font-size="10">25</text>

  <rect x="190" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="205" y="104" text-anchor="middle" fill="#fff" font-size="10">31</text>

  <rect x="225" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="240" y="104" text-anchor="middle" fill="#fff" font-size="10">42</text>

  <rect x="260" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="275" y="104" text-anchor="middle" fill="#fff" font-size="10">50</text>

  <rect x="295" y="85" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="310" y="104" text-anchor="middle" fill="#fff" font-size="10">63</text>

  <text x="330" y="104" fill="#a8dadc" font-size="11">Middle: 25 &lt; 42, search right</text>

  <!-- Step 2: Right half -->
  <text x="50" y="155" fill="#888" font-size="11" font-weight="bold">Step 2: Right Half</text>

  <rect x="225" y="170" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="240" y="189" text-anchor="middle" fill="#fff" font-size="10">42</text>

  <rect x="260" y="170" width="30" height="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
  <text x="275" y="189" text-anchor="middle" fill="#fff" font-size="10">50</text>

  <rect x="295" y="170" width="30" height="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="1"/>
  <text x="310" y="189" text-anchor="middle" fill="#fff" font-size="10">63</text>

  <text x="330" y="189" fill="#a8dadc" font-size="11">Middle: 50 &gt; 42, search left</text>

  <!-- Step 3: Found -->
  <text x="50" y="240" fill="#888" font-size="11" font-weight="bold">Step 3: Found!</text>

  <rect x="225" y="255" width="30" height="25" fill="#95e1d3" stroke="#ff6b6b" stroke-width="2"/>
  <text x="240" y="274" text-anchor="middle" fill="#fff" font-size="10">42</text>

  <text x="270" y="274" fill="#a8dadc" font-size="11">Target found in 2 steps!</text>

  <!-- Legend -->
  <text x="50" y="330" fill="#888" font-size="11">Red outline = Current middle | Blue outline = Narrowed search</text>
  <text x="50" y="350" fill="#888" font-size="11">With 8 elements, we found the target in just 2 comparisons!</text>
  <text x="50" y="370" fill="#888" font-size="11">With 1 million elements, maximum 20 comparisons needed</text>
</svg>

Each step eliminates half the remaining elements from consideration.

When to Use Binary Search

Binary Search is perfect for:

Searching sorted arrays for a specific value
Finding insertion points to keep an array sorted
Range queries on sorted data
Optimization problems where you’re searching for a threshold value
Any situation where you need O(log n) lookup after sorting

When NOT to Use It

Your data isn’t sorted (you’d need to sort first)
You need to search frequently and data changes often (overhead of sorting)
Your data structure doesn’t support random access (like linked lists)

Quiz Time

Validate what you’ve learned in this lesson by attempting these quiz questions: