Cheatsheet›Binary Search

CORE PATTERNVery High Frequency

Binary Search

Repeatedly halve the search space by comparing the midpoint against a monotonic condition. Every iteration eliminates half the remaining candidates, giving O(log N) time even for large inputs.

TimeO(log N)

SpaceO(1)

DifficultyEasy to Hard

Key Insight

Halve the problem every step — find the answer in O(log N).

Flip ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEBinary Search

Click anywhere to flip back ⟲

Recognition Signals (When to use this pattern)

→Sorted array, rotated array, or matrix
→Find target / first / last occurrence in sorted data
→Minimize the maximum or maximize the minimum (feasibility check)
→Answer lies in a monotone integer range [lo, hi]
→Square root, nth root, or real-valued binary search
→Bisect on time, capacity, or cost with a greedy validator

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

Classic Binary Search

Exact match on a sorted array — return the index or -1.

Common Problems

• Binary Search
• Search Insert Position
• Guess Number Higher or Lower
• Sqrt(x)
• First Bad Version

5 problems

Find Boundary (Left / Right Edge)

Locate the first or last index where a condition flips from false to true.

Common Problems

• Find First and Last Position of Element in Sorted Array
• First Bad Version
• Find Minimum in Rotated Sorted Array
• Search a 2D Matrix
• Peak Index in a Mountain Array

5 problems

Search in Rotated / Modified Array

Determine which half is sorted, then decide which side to discard.

Common Problems

• Search in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Find Minimum in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array II
• Find Peak Element

5 problems

Binary Search on Answer

The answer lies in a monotone range — binary search on the value, validate with a greedy check.

Common Problems

• Koko Eating Bananas
• Capacity To Ship Packages Within D Days
• Minimum Number of Days to Make m Bouquets
• Split Array Largest Sum
• Magnetic Force Between Two Balls

5 problems

Binary Search on 2D / Matrix

Map a 2D matrix to a virtual 1D sorted array and run classic binary search.

Common Problems

• Search a 2D Matrix
• Search a 2D Matrix II
• Kth Smallest Element in a Sorted Matrix
• Find a Peak Element II
• Count Negative Numbers in Sorted Matrix

5 problems

Implicit / Real-valued Binary Search

Binary search on a continuous or implicit domain — no explicit array needed.

Common Problems

• Median of Two Sorted Arrays
• Find K-th Smallest Pair Distance
• Nth Magical Number
• Minimize Max Distance to Gas Station
• Swim in Rising Water

5 problems

Template / Approach

Template for: Classic Binary Search

Set Boundaries

Initialise lo = 0 and hi = n - 1 to cover the full sorted range.

Compute Mid

mid = lo + (hi - lo) / 2 avoids integer overflow compared to (lo + hi) / 2.

Compare and Halve

If arr[mid] == target return mid. If arr[mid] < target set lo = mid + 1, else hi = mid - 1.

Return Result

Loop exits when lo > hi — target not found, return -1 (or lo for insertion point).

template_cpp

💡 Standard exact-match binary search. Use this whenever you need to find a specific value in a sorted collection. Adjust the return value to get insertion index (return lo) instead of -1 for not-found.

1// Classic binary search — sorted array, exact match
2int binarySearch(vector<int>& arr, int target)
3{
4   int lo = 0;
5   int hi = (int)arr.size() - 1;
6 
7   while (lo <= hi)
8   {
9      int mid = lo + (hi - lo) / 2;
10 
11      if (arr[mid] == target)
12      {
13         return mid;              // found
14      }
15      else if (arr[mid] < target)
16      {
17         lo = mid + 1;            // search right half
18      }
19      else
20      {
21         hi = mid - 1;            // search left half
22      }
23   }
24 
25   return -1;   // not found  (return lo for insertion index)
26}

Key Idea:Every iteration eliminates exactly half the remaining search space. With N elements you need at most ⌈log₂N⌉ + 1 comparisons — roughly 30 iterations for a billion elements.

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Easy

Binary Search

LeetCode #704

Easy

Search Insert Position

LeetCode #35

Easy

Sqrt(x)

LeetCode #69

Easy

Guess Number Higher or Lower

LeetCode #374

Medium

Find First and Last Position of Element in Sorted Array

LeetCode #34

Easy

First Bad Version

LeetCode #278

Medium

Peak Index in a Mountain Array

LeetCode #852

Medium

Find Minimum in Rotated Sorted Array

LeetCode #153

Medium

Search in Rotated Sorted Array

LeetCode #33

Medium

Search in Rotated Sorted Array II

LeetCode #81

Hard

Find Minimum in Rotated Sorted Array II

LeetCode #154

Medium

Find Peak Element

LeetCode #162

Medium

Koko Eating Bananas

LeetCode #875

Medium

Capacity To Ship Packages Within D Days

LeetCode #1011

Medium

Minimum Number of Days to Make m Bouquets

LeetCode #1482

Hard

Split Array Largest Sum

LeetCode #410

Medium

Magnetic Force Between Two Balls

LeetCode #1552

Medium

Search a 2D Matrix

LeetCode #74

Medium

Search a 2D Matrix II

LeetCode #240

Medium

Kth Smallest Element in a Sorted Matrix

LeetCode #378

Easy

Count Negative Numbers in Sorted Matrix

LeetCode #1351

Hard

Median of Two Sorted Arrays

LeetCode #4

Hard

Find K-th Smallest Pair Distance

LeetCode #719

Hard

Swim in Rising Water

LeetCode #778

Hard

Nth Magical Number

LeetCode #878

1// Classic binary search — sorted array, exact match

2int binarySearch(vector<int>& arr, int target)

4 int lo = 0;

5 int hi = (int)arr.size() - 1;

7 while (lo <= hi)

8 {

9 int mid = lo + (hi - lo) / 2;

11 if (arr[mid] == target)

12 {

13 return mid; // found

14 }

15 else if (arr[mid] < target)

16 {

17 lo = mid + 1; // search right half

18 }

19 else

20 {

21 hi = mid - 1; // search left half

22 }

23 }

25 return -1; // not found (return lo for insertion index)

26}