Algorithms · Beginner
Binary search is one of the most elegant algorithms ever written. It finds any value in a sorted list of a million items in just 20 steps. This guide shows you exactly how — with live visualizations, code in 3 languages, and a speed comparison you can feel.
Contents
- The problem binary search solves
- The “phone book” intuition
- How it works — step by step
- Live visualizer — try it yourself
- Code in Python, JavaScript & Java
- Time & space complexity
- Binary vs Linear search — the speed race
- The one rule you must not break
- Where binary search is used in real life
- Knowledge quiz
Section 01
The Problem Binary Search Solves
Imagine you have a sorted list of 1,000,000 numbers and you need to find whether the number 742,891 is in it. The naive approach — checking every single element one by one — would take up to a million comparisons in the worst case.
Binary search solves this in at most 20 comparisons. Not 20,000. Not 2,000. Twenty. That’s the power of dividing the problem in half at every step.
📌 One Requirement
Binary search only works on a sorted array. This is the most important rule. We’ll revisit why at the end.
Section 02
The Phone Book Intuition
You’ve already used binary search in real life. When you look up a name in a phone book (or a word in a dictionary), you don’t start from page 1 and flip forward.
You open to the middle. If the name you want comes alphabetically before the middle page, you throw away the right half and repeat on the left. If it comes after, you throw away the left half and repeat on the right. Each time, you eliminate half the remaining possibilities.
💡 Key Insight
Every comparison eliminates half of the remaining elements. That’s why 1,000,000 items only needs log₂(1,000,000) ≈ 20 steps. The algorithm grows with the logarithm of the input, not the input itself.
Section 03
How It Works — Step by Step
Binary search uses three pointers on the array: low, mid, and high. Here’s the algorithm:
Set low = 0, high = last index
Start with the full array in scope. Low points to the first element, high points to the last.
Calculate mid = (low + high) / 2
Find the middle index. In Python/Java use integer division: (low + high) // 2 to avoid float issues.
Compare array[mid] with target
Three possible outcomes: equal (found it! return mid), target is smaller (search left half: high = mid − 1), target is larger (search right half: low = mid + 1).
Repeat until found or low > high
If low exceeds high, the target is not in the array — return −1 (or null/None depending on your language).
⚠️ Integer Overflow Tip
In languages like Java/C++, computing (low + high) / 2 can
overflow for very large arrays. The safe formula is:
low + (high - low) / 2.
Section 04
Live Visualizer — Try It Yourself
Enter any number between 1 and 99 and watch binary search find it step by step. The yellow cell is the current midpoint being checked, grey cells are eliminated, and green means found.
Section 05
Code in Python, JavaScript & Java
Python
def binary_search(arr, target): low, high = 0, len(arr) - 1 while low <= high: mid = low + (high - low) // 2 # safe from integer overflow if arr[mid] == target: return mid # found! return the index elif arr[mid] < target: low = mid + 1 # target is in right half else: high = mid - 1 # target is in left half return -1 # not found # Example usage numbers = [2, 7, 13, 19, 25, 34, 37, 46, 58, 72] result = binary_search(numbers, 37) print(f"Found at index: {result}") # → Found at index: 6 print(binary_search(numbers, 99)) # → -1 (not found)
JavaScript
function binarySearch(arr, target) { let low = 0; let high = arr.length - 1; while (low <= high) { const mid = low + Math.floor((high - low) / 2); if (arr[mid] === target) return mid; // found if (arr[mid] < target) low = mid + 1; // search right else high = mid - 1; // search left } return -1; // not found } // Example const nums = [2, 7, 13, 19, 25, 34, 37, 46, 58, 72]; console.log(binarySearch(nums, 37)); // 6 console.log(binarySearch(nums, 99)); // -1
Java
public class BinarySearch { public static int binarySearch(int[] arr, int target) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; // avoids overflow if (arr[mid] == target) return mid; if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return -1; // not found } public static void main(String[] args) { int[] nums = {2, 7, 13, 19, 25, 34, 37, 46, 58, 72}; System.out.println(binarySearch(nums, 37)); // 6 System.out.println(binarySearch(nums, 99)); // -1 } }
Section 06
Time & Space Complexity
Binary search is one of the most efficient search algorithms. Its performance is measured using Big O notation.
| Case | Time Complexity | What it means |
|---|---|---|
| Best Case | O(1) | Target is at the midpoint on the first check |
| Average Case | O(log n) | Halves the search space each iteration |
| Worst Case | O(log n) | Target not found after exhausting all halves |
| Space (iterative) | O(1) | Only stores low, mid, high — no extra memory |
| Space (recursive) | O(log n) | Call stack grows with each recursive call |
📐 The log n explained
log₂(n) is the number of times you can halve n before reaching 1. For n = 1,024 → log₂(1024) = 10 steps. For n = 1,048,576 (1 million) → just 20 steps. Doubling the input only adds one more step.
Section 07
Binary vs Linear Search — The Speed Race
Drag the slider to set the array size and watch how many steps each algorithm needs. The difference becomes dramatic very quickly.
* Linear shows average-case (n/2). Binary shows worst-case (log₂n). Both searching the same array.
Section 08
The One Rule You Must Not Break
Binary search requires a sorted array. This is non-negotiable. Here’s why: when the algorithm looks at the midpoint and finds the target is smaller, it assumes everything to the right is also larger. In an unsorted array, that assumption is false — and the algorithm silently gives wrong answers.
# ❌ WRONG — unsorted array unsorted = [37, 2, 72, 13, 25] binary_search(unsorted, 2) # returns -1 even though 2 is there! # ✅ CORRECT — sort first sorted_arr = sorted(unsorted) # [2, 13, 25, 37, 72] binary_search(sorted_arr, 2) # returns 0 ✓ # Tip: Python has bisect module built-in for production use import bisect idx = bisect.bisect_left(sorted_arr, 2) print(sorted_arr[idx] == 2) # True
⛔ Common Mistake
Sorting takes O(n log n) time. If you’re only searching once, sorting + binary search is slower than linear search. Binary search pays off when you search the same sorted data many times — the sort cost is paid once, searches are O(log n) forever.
Section 09
Where Binary Search Is Used in Real Life
Binary search isn’t just a textbook exercise. It runs inside software you use every day.
Database Indexes
B-trees (the data structure behind MySQL, PostgreSQL indexes) use a generalized form of binary search to find rows in milliseconds across millions of records.
Package Managers
npm, pip, and apt use binary search on sorted version lists to find compatible package versions quickly.
Game Development
Finding which tile a player is on, collision detection bounds, and sorted leaderboard lookups all use binary search variants.
Spell Checkers
Dictionaries are sorted. When you type a word, spell checkers run binary search on the dictionary to verify it in O(log n) time.
Git Bisect
Git’s git bisect command uses binary search through your commit history to find which commit introduced a bug.
IP Routing
Routers use binary search on sorted prefix tables to find the right network path for packets — billions of times per second.
Section 10
Knowledge Quiz
Five questions to lock in what you’ve learned.
