Pattern #10

Binary Search

Important interview questions, thinking patterns, BS on answer, and rules for solving binary search problems in Go.

Must Solve

15 core questions — solve these first.

1.Binary Search
Basic O(log n) templateeasy
2.Search Insert Position
Find lower bound insertioneasy
3.First Bad Version
Binary Search boundary (false..true)easy
4.Guess Number Higher or Lower
Basic BS range halvingeasy
5.Find First and Last Position of Element in Sorted Array
Find boundary + keep searchingmedium
6.Search in Rotated Sorted Array
One half is always sortedmedium
7.Find Minimum in Rotated Sorted Array
Compare mid with right elementmedium
8.Find Peak Element
Compare mid with mid+1medium
9.Search a 2D Matrix
Flatten 2D matrix to 1D indexmedium
10.Koko Eating Bananas
Binary Search on Answer (speed)medium
11.Capacity To Ship Packages Within D Days
Binary Search on Answer (capacity)medium
12.Minimum Number of Days to Make m Bouquets
Binary Search on Answer (days)medium
13.Split Array Largest Sum
Binary Search on Answer (max sum)hard
14.Find K Closest Elements
Binary Search left window startmedium
15.Median of Two Sorted Arrays
Partition two arrays in halfhard

Also Important

12 more questions worth practicing.

16.Sqrt(x)
BS range [1..x]easy
17.Valid Perfect Square
BS mid * mid == numeasy
18.Peak Index in a Mountain Array
BS slope detectionmedium
19.Search in Rotated Sorted Array II
Duplicates handling (left++)medium
20.Find Minimum in Rotated Sorted Array II
Duplicates handling (right--)medium
21.Single Element in a Sorted Array
BS even/odd pair indexmedium
22.Time Based Key-Value Store
HashMap + BS timestamp listmedium
23.Successful Pairs of Spells and Potions
Sort potions + BS countmedium
24.Magnetic Force Between Two Balls
Binary Search on Answer (distance)medium
25.Aggressive Cows
Binary Search on Answer (min dist)medium
26.Allocate Minimum Number of Pages
Binary Search on Answer (pages)medium
27.Minimum Speed to Arrive on Time
Binary Search on Answer (speed)medium

How to Think

Sorted array?Binary Search
Need find one value quickly?Check middle, Discard half → O(log n)
Need first or last occurrence?Binary Search + keep searching one side
Answer is a number, not an index?Binary Search on Answer
Monotonic condition (false..false..true..true)?Binary Search the boundary

Go Thinking & Reference

Standard Binary Search Template

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2 // Avoids integer overflow
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

👉 Time: O(log n) | Space: O(1)

Binary Search on Answer

When asked for minimum speed, minimum capacity, or maximum distance:

Speed:   1  2  3  4  5  6  7  8
Status:  ❌ ❌ ❌ ❌ ✅ ✅ ✅ ✅
                     ↑
              First valid answer

💡 Binary Search can search answer ranges (e.g. [1..maxSpeed]), not just array indices!

Visual Memory Rule

Sorted Search Space
L -------- M -------- R

target < M  →  LEFT HALF (right = mid - 1)
target > M  →  RIGHT HALF (left = mid + 1)
target == M →  FOUND ✅

💡 Golden Rule: "If one decision lets you safely throw away half the search space, think Binary Search."

Common Interview Bugs to Avoid

Bug 1: Incorrect Loop Condition

Using left < right instead of left <= right without realizing if elements are missed.

Bug 2: Forgetting +1 / -1

Doing left = mid can cause infinite loops when left == right - 1.

Bug 3: Array Isn't Sorted

Normal Binary Search fails without sorted input or monotonic condition.

Bug 4: Stopping Early on Boundaries

For first/last occurrence, finding one valid value isn't enough. Keep searching the side you need.

Interview Rules

1. Sorted array? → Binary Search
2. Need O(log n) search? → Binary Search
3. First occurrence? → Find target, save ans, continue left (right = mid - 1)
4. Last occurrence? → Find target, save ans, continue right (left = mid + 1)
5. Rotated sorted array? → One half is always sorted
6. Min/max valid answer? → Binary Search on Answer
7. Monotonic `false false true true`? → Search the boundary
8. Always use mid := left + (right-left)/2 to prevent overflow

Small Rules

Rule 1: Requires useful order (sorted data or monotonic condition).
Rule 2: Each step removes half: n → n/2 → n/4 → O(log n).
Rule 3: Search space is [left, right] with loop while left <= right.
Rule 4: Mid too small: left = mid + 1. Mid too big: right = mid - 1.
Rule 5: Hardest BS problems are about finding boundaries (false false true true).

Production Thinking

Database Index Search → B-Tree / Index lookup eliminates large data partitions

Log Lookup by Time → Binary Search for first timestamp >= 10:30 AM

Git Bisect (Bug Version) → good good good bad bad → BS finds first bad commit

Server Capacity Threshold → Binary Search minimum capacity that handles workload

Remember This

Sorted                     → Binary Search
Middle too small           → Left = Mid + 1
Middle too big             → Right = Mid - 1
Each step                  → Remove half
First occurrence           → Found + keep left
Last occurrence            → Found + keep right
Minimum valid value        → Binary Search on Answer
false → false → true → true → Search the boundary

💡 Golden Rule: "If one decision lets you safely throw away half the search space, think Binary Search."