Classic Binary Search Template

The standard binary search finds a target value in a sorted array. The template uses two pointers left and right that converge toward the target. At each step, compute mid and compare it with the target to decide which half to discard.

binary_search.py O(log n) time, O(1) space
Output
Search 7: index 3 Search 1: index 0 Search 19: index 9 Search 6: index -1
Why left + (right - left) // 2 instead of (left + right) // 2?
In languages like C++ and Java, left + right can overflow if both are large integers. In Python, integers have arbitrary precision so overflow isn't an issue — but using this form is a good habit for interviews and shows you understand the pitfall.

Binary Search Step-by-Step

Let's trace binary search on the array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] searching for target 23. Each step halves the search space.

Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Step 1: left=0, right=9, mid=4 → arr[4]=16 < 23 → go right 2 5 8 12 16 23 38 56 72 91 L M R Step 2: left=5, right=9, mid=7 → arr[7]=56 > 23 → go left 2 5 8 12 16 23 38 56 72 91 L M R Step 3: left=5, right=6, mid=5 → arr[5]=23 == 23 → FOUND! 2 5 8 12 16 23 38 56 72 91 L/M R 10 elements → found in 3 steps (log₂10 ≈ 3.3) Linear search would need 6 comparisons
mid pointer left pointer / found right pointer eliminated

Left Boundary and Right Boundary Variants

The classic template finds any occurrence of the target. In interviews, you often need the first (leftmost) or last (rightmost) occurrence. These variants don't return immediately when they find the target — they keep narrowing the search space.

Left Boundary (First Occurrence)

left_boundary.py O(log n) time, O(1) space
Output
First 2: index 1 First 4: index 5 First 6: index -1

Right Boundary (Last Occurrence)

right_boundary.py O(log n) time, O(1) space
Output
Last 2: index 3 Last 4: index 6 Last 6: index -1
Pattern:
The only difference between left and right boundary is what happens when arr[mid] == target. For the left boundary, move right = mid - 1 to keep searching left. For the right boundary, move left = mid + 1 to keep searching right.

Python's bisect Module

Python's standard library provides bisect_left and bisect_right — production-grade binary search functions implemented in C. They return the insertion point for a value in a sorted list.

bisect_demo.py O(log n) time
Output
bisect_left(nums, 3) = 1 bisect_right(nums, 3) = 4 Search 5: index 4 Search 4: index -1 Count of 3: 3 Count of 5: 1 Count of 4: 0 After insort(4): [1, 3, 4, 5, 7]
Interview tip:
In a real interview, you'll usually need to implement binary search from scratch. But in production code (and in some interviews that allow it), bisect_left and bisect_right are cleaner, faster (C implementation), and less error-prone. Know both.

Binary Search on Answer

One of the most powerful (and non-obvious) applications of binary search is binary search on the answer. Instead of searching for a target in an array, you search over a range of possible answers and use a predicate function to determine if an answer is feasible.

💡
The pattern
Minimize the maximum / Maximize the minimum

The binary search on answer pattern works when:

  • You need to find the minimum value that satisfies a condition (or the maximum that doesn't).
  • The condition is monotonic: if value x works, then all values greater than x also work (or vice versa).
  • You can write a feasible(x) function that returns True/False for a given candidate answer.

The template looks like this:

binary_search_on_answer.py Template
Output
Min capacity for 5 days: 15
Why 15?
With capacity 15, the ship carries: Day 1: [1,2,3,4,5]=15, Day 2: [6,7]=13, Day 3: [8]=8, Day 4: [9]=9, Day 5: [10]=10. That's exactly 5 days. Capacity 14 would require 6 days, so 15 is the minimum.

Problem: Search in Rotated Sorted Array

LeetCode 33. Given a sorted array that has been rotated at some pivot (e.g., [4,5,6,7,0,1,2]), search for a target in O(log n). The trick: at least one half of the array around mid is always sorted.

rotated_search.py O(log n) time, O(1) space
Output
4 -1 1 0 1
Key insight:
In a rotated sorted array, when you compute mid, one of the two halves [left..mid] or [mid..right] is always sorted. Check which half is sorted, then check if the target falls within that sorted range. If it does, search that half; otherwise, search the other half. This gives O(log n).

Problem: Find First and Last Position

LeetCode 34. Given a sorted array of integers, find the starting and ending position of a given target value. If the target is not found, return [-1, -1]. Must run in O(log n).

first_last_position.py O(log n) time, O(1) space
Output
[3, 4] [-1, -1] [0, 0] [0, 1]

Problem: Integer Square Root

LeetCode 69. Given a non-negative integer x, return the integer part of its square root. This is a classic binary search on answer problem — find the largest integer n such that n * n <= x.

integer_sqrt.py O(log x) time, O(1) space
Output
sqrt(0) = 0 sqrt(1) = 1 sqrt(4) = 2 sqrt(8) = 2 sqrt(16) = 4 sqrt(27) = 5 sqrt(100) = 10
Binary search on answer:
The "answer" is in the range [1, x//2]. The predicate is mid*mid <= x. Since this predicate is monotonically decreasing (True for small mid, False for large mid), binary search finds the boundary efficiently in O(log x) time.

Problem: Find Peak Element

LeetCode 162. A peak element is strictly greater than its neighbors. Given an array where nums[i] != nums[i+1], find a peak element in O(log n). The array is not sorted — but binary search still works because of the monotonic "slope" property.

peak_element.py O(log n) time, O(1) space
Output
[1, 2, 3, 1] → peak at index 2 [1, 2, 1, 3, 5, 6, 4] → peak at index 5 [3, 2, 1] → peak at index 0 [1, 2] → peak at index 1
Why does binary search work on an unsorted array?
The key constraint is nums[-1] = nums[n] = -infinity (imaginary boundaries). This guarantees at least one peak exists. At any mid, if nums[mid] < nums[mid+1], the right half must contain a peak (ascending slope leading somewhere). Similarly for the left. This gives the monotonic property binary search needs.

Try It Yourself

First Bad Version (Binary Search on Answer)

You are a product manager. Versions 1 through n are released. One version is bad, and all versions after it are bad too. Given an API is_bad(version) that returns True if a version is bad, find the first bad version using the minimum number of API calls.

Constraint: There are n = 20 versions and version 13 is the first bad one. Use binary search to minimize calls to is_bad().

Challenge

Binary Search Challenges
Challenge 1: Search a 2D Matrix (LeetCode 74)

You're given an m x n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. Search for a target value in O(log(m*n)).

Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 returns True.

Treat the 2D matrix as a 1D sorted array of length m * n. Use standard binary search with index mapping: row = mid // n, col = mid % n. This lets you binary search over the "flattened" array without actually flattening it — O(log(m*n)) time, O(1) space.
Challenge 2: Koko Eating Bananas (LeetCode 875)

Koko has n piles of bananas. She can eat at speed k bananas per hour (one pile at a time, rounding up). Guards return in h hours. Find the minimum eating speed k so she finishes in time.

Example: piles = [3, 6, 7, 11], h = 8 returns k = 4.

This is binary search on the answer. The search space for k is [1, max(piles)]. For each candidate speed k, compute total hours needed: sum(ceil(p / k) for p in piles). If total hours <= h, then k is feasible — try smaller. Otherwise, try larger. Use math.ceil(p / k) or equivalently (p + k - 1) // k.

Quiz

Question 1 of 5
What is the time complexity of binary search on a sorted array of n elements?
Question 2 of 5
In the classic binary search template while left <= right, what happens when the target is not in the array?
Question 3 of 5
What does bisect_left([1, 3, 3, 3, 5], 3) return?
Question 4 of 5
Why can binary search be used on a rotated sorted array even though it's not fully sorted?
Question 5 of 5
In "binary search on answer" problems, what property must the predicate function have?
0
/5
Great work! You understand binary search.

Common Mistakes

  • Off-by-one in loop condition. Using while left < right instead of while left <= right in the classic template means you skip checking the last remaining element. The <= ensures the search space includes the case where left == right.
  • Infinite loop from wrong mid update. If you use while left < right with left = mid (instead of mid + 1), you get an infinite loop when left + 1 == right because mid = left never changes. Always move at least one step: left = mid + 1 or right = mid - 1.
  • Integer overflow in mid calculation. In C++ and Java, (left + right) / 2 can overflow. Use left + (right - left) / 2. Python doesn't overflow, but interviewers expect you to mention this.
  • Forgetting the sorted precondition. Binary search requires sorted data (or a monotonic property). If you apply it to an unsorted array without a valid reason (like peak element's slope property), you'll get wrong answers.
  • Wrong boundary update for boundary variants. When finding the left boundary, you must set right = mid - 1 when arr[mid] == target, not return immediately. Returning on the first match gives you any occurrence, not the first one.

Key Takeaways

  • Classic binary search uses while left <= right and returns when arr[mid] == target. Time: O(log n), Space: O(1). Master this template first — it's the foundation for all variants.
  • Boundary variants find the first or last occurrence by continuing the search even after finding the target. The only change: update right = mid - 1 (left boundary) or left = mid + 1 (right boundary) when arr[mid] == target.
  • Python's bisect module provides bisect_left and bisect_right — use them in production code for clean, bug-free binary search. Count occurrences in O(log n) with bisect_right(x) - bisect_left(x).
  • Binary search on answer is the most powerful pattern: define a search space of possible answers, write a feasible(x) predicate, and binary search for the boundary. Solves "minimize the maximum" / "maximize the minimum" problems.
  • Binary search works beyond sorted arrays — rotated arrays, peak elements, and any problem with a monotonic property. The key question: "Can I eliminate half the search space with one comparison?"
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've mastered binary search.
Now search for the right career move.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →