MediumVery High Frequency

Binary Search Pattern

Think about opening a dictionary to find the word “Mango.” You open to the middle, see “N”, go slightly left. Each flip halves the remaining pages. That is binary search — the single most important search technique in computer science, reducing O(n) lookups to O(log n).

Tested at:GoogleMetaAmazonAppleMicrosoft

Target: 5mid=7 > 5, go left

Pattern Recognition

When to Use Binary Search

Use binary search whenever you can eliminate half of the remaining candidates with a single comparison. The data does not have to be a sorted array — it just needs a monotonic condition that lets you decide which half to discard.

Trigger Phrases

When you spot any of these in an interview question, immediately think binary search:

"sorted array"

Classic binary search territory

"find the position of"

Searching for an index or value

"minimize/maximize value with condition"

Binary search on answer

"rotated sorted array"

Modified binary search

"search space can be halved"

Core invariant of binary search

"O(log n) required"

Only binary search achieves this for search

"first/last occurrence"

Lower bound / upper bound variant

"smallest value that satisfies"

Binary search on answer

Decision Flowchart

IS Binary Search

✓Finding a target in a sorted array
✓Finding minimum speed/capacity satisfying a condition
✓Finding a peak element in a unimodal array
✓Searching in a rotated sorted array
✓Finding first/last position of an element

IS NOT Binary Search

✗Finding element in unsorted array (use hash map)
✗Finding all pairs/combinations (two pointers or backtracking)
✗Graph/tree traversal problems (use BFS/DFS)
✗No clear "go left or right" rule definable
✗Counting distinct subsequences (use DP)

Deep Dive: Why Binary Search?

The Real-World Analogy

Imagine you are playing a number guessing game. Your friend picks a number between 1 and 1000 and after each guess tells you “higher” or “lower.”

Bad Strategy: Linear Guess

Guess 1, 2, 3, 4, ... in order.

Worst case: 1000 guesses

If the number is 873, you waste 872 guesses before getting close.

Smart Strategy: Binary Search

Guess 500. “Higher.” Guess 750. “Lower.” Guess 625...

Worst case: 10 guesses

Each guess eliminates half the remaining numbers. 1000 → 500 → 250 → ... → 1.

This is exactly what binary search does. A dictionary with 100,000 words? You find any word in at most 17 lookups. A database with 1 billion records? At most 30 lookups. That is the power of halving.

What O(log n) Really Means in Practice

Candidates throw around “O(log n)” without appreciating how absurdly fast it is. Here is the perspective that will change your intuition:

n (input size)	O(n) steps	O(log n) steps	Speedup
100	100	7	14x
10,000	10,000	14	714x
1,000,000	1,000,000	20	50,000x
1,000,000,000	1,000,000,000	30	33,000,000x

The Mental Model

Every time the input size doubles, binary search only needs one more step. Going from 1 million to 2 million elements? That is just one extra comparison. Going from 1 million to 1 billion elements? Only 10 more comparisons. This is why binary search scales to planet-sized datasets.

Visual Mental Model: Eliminating Half Each Step

Think of binary search as a funnel. You start with n candidates and the funnel narrows by half each step. The key insight is that you are not searching -- you are eliminating.

Start

1024

After 1 comparison

512

After 2 comparisons

256

After 3 comparisons

128

After 5 comparisons

After 10 comparisons

Starting with 1024 elements, binary search reaches a single candidate in just 10 comparisons. Linear search would need up to 1024.

The Four Critical Variations

Every binary search problem you encounter in interviews falls into one of these four categories. Master these four and you have complete coverage.

Standard Binary Search

Find an exact value in a sorted array.

Template: lo <= hi, return on match

Examples: LeetCode 704, search in sorted matrix

Boundary Search (bisect left/right)

Find the first or last position satisfying a condition. Handles duplicates.

Template: lo < hi, narrow on match

Examples: First/last occurrence, insertion point

Binary Search on Answer

Minimize/maximize a value that satisfies a monotonic constraint. The answer is not in any array.

Template: lo < hi + feasibility function

Examples: Koko Eating Bananas, Ship Packages

Modified Binary Search

Rotated arrays, peak elements, or any structure with a hidden sorted property.

Template: Varies. Identify which half is sorted, then decide.

Examples: Rotated array search, Find Peak, Find Min in Rotated

The One Rule of Binary Search

Binary search works whenever there is a monotonic predicate over the search space. This means: there exists a function f(x) that is false, false, ..., true, true (or vice versa) as x increases. The array does NOT need to be literally sorted. It just needs to have a “tipping point” you can binary search for. Once you internalize this, problems like “Koko Eating Bananas” or “Find Peak Element” become obvious binary search applications.

Visual Walkthrough

Standard Search: Find 9 in a Sorted Array

Finding 9 in [1, 3, 5, 7, 9, 11, 13]:

135791113

arr[3]=7 < 9 Search right half

135791113

arr[5]=11 > 9 Search left half

135791113

arr[4]=9 == 9 Found at index 4!

Only 3 comparisons instead of 7 with linear scan. That is O(log n) vs O(n).

Search on Answer: Koko Eating Bananas

Koko has piles [3, 6, 7, 11] and 8 hours. What is the minimum eating speed?

Search Space

1...456...11

Low = 1, High = max(piles) = 11

Binary Search Logic

mid=6: hours = 1+1+2+2 = 6 ≤ 8 → try smaller
mid=3: hours = 1+2+3+4 = 10 > 8 → too slow
mid=4: hours = 1+2+2+3 = 8 ≤ 8 → answer = 4

The answer is not in the array. You binary search over the space of possible answers.

Interactive Walkthrough: Find 23 in Sorted Array

Watch binary search halve the search space with each comparison. Gray cells are eliminated, colored cells remain in play.

1 / 5

Initialize: left=0, right=9. Search space is the entire array [2..91]. Calculate mid = floor((0+9)/2) = 4.

left=0, right=9, mid=4, arr[4]=16

Templates

Three reusable skeletons that cover every binary search variation you will encounter. Memorize these, and you can solve any binary search problem.

Template 1: Standard Binary Search

Find a target value in a sorted array. Returns the index or -1.

Standard Binary Search

1def binary_search(nums, target):
2    # ---- SECTION 1: INITIALIZATION ----
3    # WHY len-1? right is the last valid index. The search space is [left, right] inclusive.
4    left, right = 0, len(nums) - 1
5
6    # ---- SECTION 2: MAIN LOOP ----
7    # WHY <=? We need to check when left == right (single element remaining).
8    # With < instead of <=, we would skip the last candidate.
9    while left <= right:
10        mid = left + (right - left) // 2  # WHY not (left+right)//2? Avoids integer
11                                           # overflow in Java/C++. Safe habit everywhere.
12
13        # ---- SECTION 3: DECISION LOGIC ----
14        if nums[mid] == target:
15            return mid             # Found — return immediately
16        elif nums[mid] < target:
17            left = mid + 1         # WHY mid+1? mid is already checked and too small.
18                                   # Including it again would be wasted work.
19        else:
20            right = mid - 1        # WHY mid-1? mid is too large, exclude it.
21
22    # ---- SECTION 4: RETURN ----
23    # WHY -1? Loop ended with left > right — search space is empty, target not found.
24    return -1

Template Breakdown

Initialization

left = 0, right = len-1. The search space is [left, right] inclusive. Every candidate index lives in this range.

Loop (while left <= right)

The <= is critical. When left == right, there is one candidate left to check. Using < would skip it, causing missed results.

Decision: mid+1 / mid-1

We use mid + 1 and mid - 1 because mid is already checked. Including it again would not shrink the search space, risking an infinite loop.

Return -1

If left > right, the search space collapsed to empty. The target does not exist in the array.

How to Apply This Template

Step 1: Verify the input is sorted (or sortable). Binary search requires monotonic order.
Step 2: Define what “found” means. Exact match? Closest value? First occurrence?
Step 3: For exact match, use this template as-is. For boundaries (first/last), switch to Template 2.

Template 2: Lower Bound / Upper Bound

Find the first position where condition(mid) is true. Works for first/last occurrence, insertion point, and more.

Lower Bound (First True)

1def lower_bound(nums, target):
2    """First index where nums[i] >= target."""
3    # WHY right = len(nums), not len-1? Because the answer could be
4    # "past the end" if all elements are < target (insertion point).
5    left, right = 0, len(nums)
6
7    # WHY < not <=? We converge left and right to the SAME index.
8    # When left == right, that IS the answer — no need to check further.
9    while left < right:
10        mid = left + (right - left) // 2
11        if nums[mid] >= target:
12            right = mid    # WHY mid not mid-1? mid MIGHT be the answer.
13                           # We cannot exclude it — only narrow the range.
14        else:
15            left = mid + 1 # mid is too small — definitely not the answer.
16    return left  # left == right == first index where nums[i] >= target
17
18def upper_bound(nums, target):
19    """First index where nums[i] > target."""
20    left, right = 0, len(nums)
21    while left < right:
22        mid = left + (right - left) // 2
23        if nums[mid] > target: right = mid   # WHY > not >=? That is
24        else: left = mid + 1  # the only change from lower_bound
25    return left

Template 1 vs Template 2: The Key Differences

Aspect	Template 1	Template 2
Loop condition	left <= right	left < right
Right init	len - 1	len (past end)
On match	Return immediately	Keep narrowing (right = mid)
Use case	Exact match	First/last occurrence, insertion point

How to Apply This Template

Step 1: Define the condition: >= for lower bound, > for upper bound. For “last occurrence,” use upper_bound - 1.
Step 2: Set right = len(nums) (not len-1) because the answer might be past the end.
Step 3: Use right = mid (not mid-1) because mid might be the answer. This is the critical difference from Template 1.

Template 3: Search on Answer

When the answer is not in the array but within a range. Binary search over the answer space using a feasibility check.

Binary Search on Answer (Minimize)

1def search_on_answer(lo, hi, is_feasible):
2    """Min value in [lo, hi] where is_feasible is True."""
3    # WHY same structure as lower_bound? Because we are finding the first
4    # value where is_feasible flips from False to True — same concept,
5    # but over an answer space instead of array indices.
6    while lo < hi:
7        mid = lo + (hi - lo) // 2
8        if is_feasible(mid): hi = mid  # WHY hi=mid? It works, but maybe a
9                                        # smaller value also works — keep searching left
10        else: lo = mid + 1             # WHY lo=mid+1? This value is too small
11                                        # to satisfy the constraint — exclude it
12    return lo  # lo == hi == smallest feasible value
13
14# Example: Koko Eating Bananas
15def min_eating_speed(piles, h):
16    def can_finish(speed):
17        # WHY (p + speed - 1) // speed? Ceiling division without floats.
18        # Each pile of size p takes ceil(p/speed) hours to eat.
19        return sum((p + speed - 1) // speed for p in piles) <= h
20    # WHY range [1, max(piles)]? Speed 1 is minimum possible, max(piles)
21    # always works in len(piles) hours (each pile takes exactly 1 hour).
22    return search_on_answer(1, max(piles), can_finish)

Template Breakdown

Define the Search Space

[lo, hi] is the range of possible answers. For Koko: speed from 1 (minimum) to max(piles) (always works). For ship capacity: max weight to sum of all weights.

Write the Feasibility Function

is_feasible(mid) returns True if the value mid satisfies the constraint. This function must be monotonic: once True, it stays True for all larger values.

Binary Search the Transition

The answer space looks like: [F, F, F, ..., T, T, T]. We find the first T. This is exactly lower_bound applied to the answer space.

How to Apply This Template

Step 1: Define lo and hi. What is the minimum and maximum possible answer?
Step 2: Write is_feasible(mid). Simulate the problem with this candidate answer. Does it satisfy the constraint?
Step 3: For minimize: use hi = mid when feasible. For maximize: flip the condition and use lo = mid (and mid = lo + (hi - lo + 1) // 2 to avoid infinite loop).

The Core Idea

Every binary search problem reduces to: define a boolean function f(x) that is false, false, ..., true, true as x increases. Binary search finds the transition point. Standard search, bounds, and search-on-answer are all instances of this single pattern.

The Definitive Guide: `lo <= hi` vs `lo < hi`

This is the #1 source of confusion and bugs in binary search. Here is the complete mental model so you never get it wrong again.

`while lo <= hi`

The “check every candidate” loop

Search space:

[lo, hi] inclusive. Both endpoints are valid candidates.

Terminates when:

lo > hi -- the search space is empty. Every candidate has been checked.

On match:

Return immediately. You found the answer.

Pointer updates:

lo = mid + 1 and hi = mid - 1. You exclude mid because you already checked it.

Use when:

Finding an exact match. Searching in rotated arrays (where you return on match).

init: lo=0, hi=len-1

loop: while lo <= hi

shrink: mid+1 / mid-1

return: inside loop (found) or -1 (not found)

`while lo < hi`

The “converge to answer” loop

Search space:

[lo, hi] inclusive, but lo and hi converge to the same index.

Terminates when:

lo == hi -- they point to the answer. No need to check further.

On match:

Do NOT return. Keep narrowing. The answer is the boundary, not the first match you find.

Pointer updates:

lo = mid + 1 (exclude mid) but hi = mid (keep mid as candidate). Because mid might be the answer.

Use when:

Finding boundaries (first/last occurrence), minimizing/maximizing values, finding peaks or rotation points.

init: lo=0, hi=len (or len-1)

loop: while lo < hi

shrink: mid+1 / mid (NOT mid-1)

return: lo (== hi) after loop

The Infinite Loop Trap

When using lo < hi, if you write lo = mid (instead of lo = mid + 1), you MUST compute mid as lo + (hi - lo + 1) / 2 (round UP). Otherwise, when hi = lo + 1, mid rounds down to lo, and lo = mid makes no progress -- infinite loop. This only matters when maximizing. When minimizing (the common case), you use hi = mid and lo = mid + 1, which is always safe.

Quick Decision Cheat Sheet

“Do I need to find an exact value and return it?”

Yes → use lo <= hi with return mid on match.

“Do I need to find the boundary / first true / min feasible / peak?”

Yes → use lo < hi with return lo after loop.

“Should I use mid+1 or mid when updating hi?”

If you already checked mid and it is wrong: hi = mid - 1. If mid might be the answer: hi = mid.

Variations

Variation	Use When	Template	Key Difference
Standard find target	Exact match in sorted array	`left <= right`	Return on match
First / last occurrence	Duplicates present, need boundary	`left < right`	Do not return on match, keep narrowing
Search on answer	Minimize / maximize a value	`left < right`	Search over answer space, not array
Rotated sorted array	Array was sorted then rotated	`left <= right`	Check which half is sorted first
Peak element	Find local max in unsorted array	`left < right`	Compare mid with mid+1

Decision Guide

Need exact match? Use Template 1 (left <= right).
Need first/last or insertion point? Use Template 2 (left < right).
Answer is a value, not an index? Use Template 3 (search on answer).
Array is rotated? Modify Template 1 with a sorted-half check.

Worked Examples

1. Binary Search

EasyLeetCode 704

Given a sorted array nums and a target, return its index or -1.

Think Before You Code

1.What property of the input lets us eliminate candidates? (It is sorted.)
2.What do we compare to decide left vs right? (Compare mid element to target.)
3.What is the loop invariant? (Target, if it exists, is always in [left, right].)
4.When do we stop? (Found target, or search space is empty.)

Brute Force: Linear Scan

Iterate through every element. Return index when found.

for i in range(len(nums)): if nums[i] == target: return i

Time: O(n)Space: O(1)

Why suboptimal: Ignores the fact that the array is sorted. We can do much better by exploiting order.

Intuition Bridge: The “Aha” Moment

The array is sorted. If the middle element is too small, every element to its left is also too small. One comparison eliminates half the array. Repeat this logic until the target is found or the search space is empty. This is the purest form of binary search.

Why Binary Search?

The array is sorted. Discard half per comparison. Textbook Template 1 application.

1L=0 R=5 M=2arr[2]=3 < 9, go right

2L=3 R=5 M=4arr[4]=9 == 9, found!

LeetCode 704

1def search(nums, target):
2    left, right = 0, len(nums) - 1  # Search space: all valid indices
3    while left <= right:             # WHY <=? Must check single-element case
4        mid = left + (right - left) // 2  # Overflow-safe midpoint
5        if nums[mid] == target: return mid      # Found — done
6        elif nums[mid] < target: left = mid + 1 # Target in right half
7        else: right = mid - 1                    # Target in left half
8    return -1  # Search space empty — target not present

Dry Run: nums = [-1, 0, 3, 5, 9, 12], target = 9

Step	left	right	mid	nums[mid]	Action
1	0	5	2	3	3 < 9 → left = 3
2	3	5	4	9	Found! Return 4

Only 2 comparisons for a 6-element array. Linear scan would take up to 6.

Key Line Spotlight

mid = left + (right - left) // 2

This is the overflow-safe version of (left + right) // 2. In Python, integers have arbitrary precision so overflow is not a concern. But in Java and C++, left + right can exceed Integer.MAX_VALUE. Using left + (right - left) / 2 avoids this. Build the habit in every language.

Why O(log n)?

Each iteration halves the search space: n → n/2 → n/4 → ... → 1. The number of halvings to reach 1 is log2(n). Each step does O(1) work, so total = O(log n).

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

2. Search in Rotated Sorted Array

MediumLeetCode 33

A sorted array was sorted in ascending order, then rotated at some unknown pivot. Given a target, find it in O(log n). No duplicates.

Think Before You Code

1.The array is not fully sorted. Can binary search still work? (Yes -- at least one half is always sorted.)
2.How do we identify the sorted half? (Compare nums[left] with nums[mid].)
3.Once we know the sorted half, how do we decide where the target is? (Check if target is within the sorted half's range.)

Brute Force: Linear Scan

Ignore the rotation and scan every element. O(n).

Why suboptimal: Completely ignores the partially-sorted structure. The question explicitly asks for O(log n).

Intuition Bridge

A rotated sorted array like [4, 5, 6, 7, 0, 1, 2] always has one property: if you pick any mid, one of the two halves [left..mid] or [mid..right] is guaranteed to be sorted. In the sorted half, you can do a simple range check to decide if the target lives there. If not, it must be in the other half. This gives you O(log n).

Why Binary Search?

At every step one half is guaranteed sorted. Check if target falls in the sorted half; otherwise search the other half.

4567012

Cyan = left sorted, Amber = right sorted, Green = target

LeetCode 33

1def search(nums, target):
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        mid = left + (right - left) // 2
5        if nums[mid] == target: return mid
6
7        # WHY check nums[left] <= nums[mid]? This tells us the LEFT half
8        # [left..mid] is sorted (no rotation point in this half).
9        if nums[left] <= nums[mid]:          # Left half is sorted
10            # WHY two conditions? target must be WITHIN the sorted range
11            # [nums[left], nums[mid]) to safely search left
12            if nums[left] <= target < nums[mid]:
13                right = mid - 1  # Target in sorted left half
14            else: left = mid + 1 # Target must be in right (unsorted) half
15        else:                                 # Right half is sorted
16            if nums[mid] < target <= nums[right]:
17                left = mid + 1   # Target in sorted right half
18            else: right = mid - 1 # Target in left (unsorted) half
19    return -1

Key Line Spotlight

if nums[left] <= nums[mid]

This comparison determines which half is sorted. In a rotated array, at least one half is always sorted. By identifying the sorted half, we can use standard range-checking to decide where the target lies. The <= (not <) handles the case where left equals mid (odd-length arrays).

Dry Run: nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Step	left	right	mid	nums[mid]	Sorted half?	Action
1	0	6	3	7	Left [4,5,6,7] sorted	0 not in [4,7] → left=4
2	4	6	5	1	Right [1,2] sorted	0 not in (1,2] → right=4
3	4	4	4	0	-	Found! Return 4

3 steps to find the target at the rotation point. The key: always identify the sorted half first, then check if target is within its range.

Common Mistake: Forgetting the = in nums[left] <= nums[mid]

Using < instead of <= fails when left == mid (e.g., 2-element subarray). When nums[left] == nums[mid], the “left half” is just one element, and it is sorted. The = correctly identifies this.

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

3. Find Minimum in Rotated Sorted Array

MediumLeetCode 153

A sorted array was rotated between 1 and n times. Find the minimum element. All elements are unique.

Think Before You Code

1.We are NOT looking for a target. We are looking for a structural property -- the rotation point.
2.Which template? We need to converge to the minimum, not return on match. → Template 2: lo < hi
3.Should we compare mid with left or right? (Right. Comparing with left is ambiguous when the array is not rotated.)

Brute Force: Linear Scan

Use min(nums) or scan for the first element smaller than its predecessor. O(n).

Why suboptimal: The partially-sorted structure allows O(log n).

Intuition Bridge

In a rotated sorted array, the minimum is at the “drop” point -- where a larger element is followed by a smaller one. If nums[mid] > nums[right], the drop must be somewhere in [mid+1, right]. Otherwise, the subarray [mid, right] is sorted, and the minimum is at or before mid. We converge to it.

Why Compare with right, Not left?

Comparing with nums[left] is ambiguous. Consider [1, 2, 3] (not rotated): nums[mid] > nums[left] but the minimum IS at the left. Comparing with nums[right] always gives a clear signal: if mid > right, the rotation point is on the right side.

34512

LeetCode 153

1def find_min(nums):
2    left, right = 0, len(nums) - 1
3    # WHY left < right (not <=)? We converge to the single minimum element.
4    # When left == right, we have found it.
5    while left < right:
6        mid = left + (right - left) // 2
7        # WHY compare mid with right (not left)? Because if we used left,
8        # we could not distinguish "sorted" from "minimum is at left".
9        # Comparing with right clearly tells us: if mid > right, the
10        # rotation point (minimum) is in the right half.
11        if nums[mid] > nums[right]: left = mid + 1  # Min is in right half
12        else: right = mid  # WHY mid not mid-1? mid could BE the minimum
13    return nums[left]  # left == right == index of minimum

Key Line Spotlight

if nums[mid] > nums[right]: left = mid + 1

When nums[mid] > nums[right], there must be a “drop” somewhere between mid and right (the rotation point). So the minimum is in [mid+1, right]. Otherwise, the subarray [mid, right] is sorted, and the minimum is at or before mid.

Dry Run: nums = [3, 4, 5, 1, 2]

Step	left	right	mid	nums[mid]	vs nums[right]	Action
1	0	4	2	5	5 > 2	Drop is right → left = 3
2	3	4	3	1	1 < 2	Sorted → right = 3
3	3	3	left == right		Return nums[3] = 1

Only 2 comparisons for a 5-element array. Notice how we used lo < hi (Template 2) since we are converging to a boundary, not searching for an exact match.

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

4. Koko Eating Bananas

MediumLeetCode 875

Koko loves eating bananas. There are n piles. The guards will come back in h hours. Find the minimum integer eating speed k such that she can eat all bananas within h hours.

Think Before You Code

1.There is no sorted array here. Is this even binary search? (Yes -- we binary search over the answer space.)
2.What is the search space? (Speed from 1 to max(piles). Speed = 1 is the minimum. Speed = max(piles) always finishes in n hours.)
3.Is the feasibility monotonic? (Yes. If speed k finishes in time, speed k+1 also finishes. F,F,...,T,T pattern.)
4.Are we minimizing or maximizing? (Minimizing. Use hi = mid when feasible.)

Brute Force: Try Every Speed

Test speed = 1, 2, 3, ..., max(piles). Return the first speed where total hours ≤ h.

Time: O(n * max(piles))Space: O(1)

Why suboptimal: max(piles) can be up to 10^9. Checking each speed linearly is far too slow. Binary search reduces it to O(n log(max(piles))).

Intuition Bridge: The “Aha” Moment

Think of the answer space as a boolean array: for each speed, ask “Can Koko finish in time?” The array looks like [F, F, F, ..., T, T, T]. We want the first T. This is exactly the lower_bound pattern (Template 3) applied to a conceptual array instead of a real one.

Why Binary Search on Answer?

Feasibility is monotonic: if speed k works, any speed > k also works. The answer space [1, max(piles)] has the [F, F, ..., T, T] structure. Binary search finds the transition point.

LeetCode 875

1import math
2
3def min_eating_speed(piles, h):
4    def can_finish(speed):
5        # WHY ceil(p/speed)? Each pile takes ceil(p/speed) hours.
6        # Even 1 banana left in a pile costs a full hour.
7        return sum(math.ceil(p / speed) for p in piles) <= h
8
9    lo, hi = 1, max(piles)  # WHY this range? Speed 1 = slowest possible.
10                              # Speed max(piles) = 1 hour per pile, always works.
11    while lo < hi:
12        mid = lo + (hi - lo) // 2
13        if can_finish(mid): hi = mid  # Works — but maybe slower speed also works
14        else: lo = mid + 1            # Too slow — need to eat faster
15    return lo  # Minimum speed that lets Koko finish in h hours

Dry Run: piles = [3, 6, 7, 11], h = 8

lo	hi	mid	hours at mid	Action
1	11	6	1+1+2+2=6	6 ≤ 8 → hi = 6
1	6	3	1+2+3+4=10	10 > 8 → lo = 4
4	6	5	1+2+2+3=8	8 ≤ 8 → hi = 5
4	5	4	1+2+2+3=8	8 ≤ 8 → hi = 4. lo==hi, return 4

Key Line Spotlight

if can_finish(mid): hi = mid

When can_finish returns True, we do not return immediately. A slower speed (smaller value) might also work. By setting hi = mid, we keep the current speed as a candidate but continue searching for a smaller one. This is the “minimize feasible value” pattern.

Why O(n log m)?

Binary search: The search space is [1, max(piles)] = m values. Binary search takes O(log m) iterations.
Feasibility check: can_finish(mid) iterates through all n piles → O(n) per call.
Total: O(log m) iterations * O(n) per iteration = O(n log m).

Time: O(n log m) where m = max(piles)Space: O(1)

5. Find Peak Element

MediumLeetCode 162

A peak element is strictly greater than its neighbors. Given an array nums, find a peak element and return its index. The array may contain multiple peaks; return any of them. nums[-1] = nums[n] = -infinity. Must be O(log n).

Think Before You Code

1.The array is NOT sorted. Can we still use binary search? (Yes -- but we need a different “halving” strategy.)
2.What monotonic property exists? (If nums[mid] < nums[mid+1], there MUST be a peak to the right -- the array rises, and since nums[n] = -infinity, it must come back down.)
3.Which template? We converge to the peak, so lo < hi (Template 2).)
4.Why does this guarantee a peak? (By always moving toward the higher neighbor, we “climb” toward a peak. The boundary conditions ensure one always exists.)

Brute Force: Linear Scan

Check each element: if nums[i] > nums[i-1] and nums[i] > nums[i+1], it is a peak. Or simply find the global max.

Time: O(n)Space: O(1)

Why suboptimal: The question demands O(log n). The hill-climbing property lets us apply binary search.

Intuition Bridge: The “Aha” Moment

Imagine standing on a mountain trail. You look at the slope at your feet. If the ground rises to the right, there MUST be a peak somewhere to your right (because the trail ends at -infinity). If it rises to the left, the peak is to your left. Either way, you can eliminate half the trail each step. You do not need the array to be sorted -- you just need to be able to “walk uphill.”

Why Binary Search?

At mid, compare nums[mid] with nums[mid+1]. If rising, peak is to the right. If falling, peak is to the left (or at mid). The boundary conditions nums[-1] = nums[n] = -infinity guarantee a peak exists in whichever direction the slope rises.

1231

Green = peak element (index 2). The array rises then falls -- the peak is where the direction changes.

LeetCode 162 — Find Peak Element

1def find_peak_element(nums):
2    left, right = 0, len(nums) - 1
3
4    # WHY left < right? We converge to the peak — when left == right,
5    # that IS the peak. No need to check further.
6    while left < right:
7        mid = left + (right - left) // 2
8
9        # Compare mid with its right neighbor
10        if nums[mid] < nums[mid + 1]:
11            # Rising slope — a peak MUST exist to the right.
12            # WHY? Because nums[n] = -inf, so the slope must come
13            # back down somewhere in [mid+1, right].
14            left = mid + 1  # mid is NOT the peak (it is lower than mid+1)
15        else:
16            # Falling slope or equal — peak is at mid or to the left.
17            # WHY right = mid (not mid-1)? Because mid itself could be
18            # the peak. We cannot exclude it.
19            right = mid
20
21    return left  # left == right == peak index

Dry Run: nums = [1, 2, 1, 3, 5, 6, 4]

Step	left	right	mid	nums[mid] vs nums[mid+1]	Action
1	0	6	3	3 < 5 (rising)	Peak is right → left = 4
2	4	6	5	6 > 4 (falling)	Peak at mid or left → right = 5
3	4	5	4	5 < 6 (rising)	Peak is right → left = 5
4	5	5	left == right		Return 5 (nums[5]=6)

Found peak at index 5 (value 6) in 3 comparisons for a 7-element array. Note: index 1 (value 2) is also a valid peak -- the problem only requires returning any peak.

Key Line Spotlight

if nums[mid] < nums[mid + 1]: left = mid + 1

This is the “hill climbing” step. If mid is lower than mid+1, we move right (uphill). Since nums[n] = -infinity, the slope MUST come back down eventually, guaranteeing a peak in [mid+1, right]. We do not compare with mid-1 because comparing with mid+1 alone is sufficient -- it creates a clean binary decision.

Common Mistake: Using lo <= hi

If you use lo <= hi and try to access nums[mid+1] when mid == right, you get an index-out-of-bounds error. The lo < hi template guarantees mid < right, so mid+1 is always valid.

Why This is NOT Obvious Binary Search

This problem is tricky because the array is not sorted. The “aha” is realizing you do not need global order -- you only need a local directional signal at each step. If mid < mid+1, the peak is right. If mid > mid+1, the peak is left (or at mid). This local signal lets you eliminate half the array each time, which is the essence of binary search.

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

Common Mistakes & Pro Tips

Off-by-One: left <= right vs left < right

left <= right processes every element; return inside the loop on exact match. left < right converges to one element; use for boundary (first true, min feasible). Mixing them causes infinite loops or missed elements.

Integer Overflow in mid Calculation

Never write mid = (left + right) / 2 in Java/C++. If left + right exceeds Integer.MAX_VALUE, you get overflow. Always use mid = left + (right - left) / 2.

Wrong Condition for Moving Pointers

When searching for the first occurrence, writing right = mid - 1 instead of right = mid skips the answer. Trace through a 2-element array to verify your pointer updates.

Pro Tip: The 2-Element Test

After writing your binary search, mentally test it with an array of size 2. Does it converge? Does it skip the answer? Does it infinite-loop? This single test catches almost all off-by-one bugs.

Pro Tip: State the Invariant Out Loud

Before coding, tell the interviewer: “My invariant is that the answer is always in [left, right].” This frames your solution clearly and interviewers love candidates who articulate their thinking.

Pro Tip: When in Doubt, Use Template 2

The left < right template with right = mid and left = mid + 1 is the safest general-purpose template. It never infinite-loops and converges to the exact boundary.

The 2-Element Test in Practice

Here is exactly how to verify your binary search with a 2-element array. Do this every time before submitting.

Test: [1, 3], target = 3

lo=0, hi=1, mid=0

nums[0]=1 < 3 → lo=1

lo=1, hi=1, mid=1

nums[1]=3 == 3 → return 1

Correct.

Test: [1, 3], target = 2 (not found)

lo=0, hi=1, mid=0

nums[0]=1 < 2 → lo=1

lo=1, hi=1, mid=1

nums[1]=3 > 2 → hi=0

lo=1 > hi=0 → return -1

Correct.

If both tests pass, your implementation is almost certainly correct. This takes 30 seconds and prevents the most common interview mistakes.

Binary Search Debugging Checklist

Something wrong? Check these in order:

1.Infinite loop? Check that the search space shrinks every iteration. lo = mid without rounding up causes this.

2.Off by one? Trace with a 1-element array and a 2-element array. If either fails, your loop condition or pointer update is wrong.

3.Wrong answer? Check if you should be returning lo, hi, or mid. After lo < hi loop, the answer is lo (== hi).

4.Index out of bounds? If you access mid+1, ensure mid < len-1. The lo < hi template guarantees this when hi = len-1.

5.Overflow? Use lo + (hi - lo) / 2, never (lo + hi) / 2 in typed languages.

Interviewer's Perspective

What Interviewers Are Really Testing

1.Can you recognize binary search applicability? Many problems don't mention “sorted array.” The key tell is a monotonic predicate: if the answer works for value X, it works for all values ≥ X (or ≤ X). This means you can binary search on the answer.
2.Can you handle the edge cases correctly? Off-by-one errors in binary search are the #1 interview failure mode. Interviewers want to see you trace through a 2-element array before declaring your solution correct.
3.Do you have ONE consistent template? Candidates who switch between lo <= hi and lo < hi mid-problem make mistakes. Pick one, know its invariant, and apply it consistently.

Binary Search Pattern

Pattern Recognition

Trigger Phrases

Decision Flowchart

IS Binary Search

IS NOT Binary Search

Deep Dive: Why Binary Search?

The Real-World Analogy

Bad Strategy: Linear Guess

Smart Strategy: Binary Search

What O(log n) Really Means in Practice

Visual Mental Model: Eliminating Half Each Step

The Four Critical Variations

Standard Binary Search

Boundary Search (bisect left/right)

Binary Search on Answer

Modified Binary Search

Visual Walkthrough

Standard Search: Find 9 in a Sorted Array

Search on Answer: Koko Eating Bananas

Interactive Walkthrough: Find 23 in Sorted Array

Templates

Template 1: Standard Binary Search

Template Breakdown

Template 2: Lower Bound / Upper Bound

Template 1 vs Template 2: The Key Differences

Template 3: Search on Answer

Template Breakdown

The Definitive Guide: lo <= hi vs lo < hi

while lo <= hi

while lo < hi

Quick Decision Cheat Sheet

Variations

Worked Examples

1. Binary Search

Think Before You Code

Brute Force: Linear Scan

Intuition Bridge: The “Aha” Moment

Dry Run: nums = [-1, 0, 3, 5, 9, 12], target = 9

Why O(log n)?

2. Search in Rotated Sorted Array

Think Before You Code

Brute Force: Linear Scan

Intuition Bridge

Dry Run: nums = [4, 5, 6, 7, 0, 1, 2], target = 0

3. Find Minimum in Rotated Sorted Array

Think Before You Code

Brute Force: Linear Scan

Intuition Bridge

Dry Run: nums = [3, 4, 5, 1, 2]

4. Koko Eating Bananas

Think Before You Code

Brute Force: Try Every Speed

Intuition Bridge: The “Aha” Moment

Dry Run: piles = [3, 6, 7, 11], h = 8

Why O(n log m)?

5. Find Peak Element

Think Before You Code

Brute Force: Linear Scan

Intuition Bridge: The “Aha” Moment

Dry Run: nums = [1, 2, 1, 3, 5, 6, 4]

Why This is NOT Obvious Binary Search

Common Mistakes & Pro Tips

The 2-Element Test in Practice

Binary Search Debugging Checklist

Interviewer's Perspective

Related Patterns

Two Pointers

Divide and Conquer

Binary Search Concept

Sorting Concept

The Definitive Guide: `lo <= hi` vs `lo < hi`

`while lo <= hi`

`while lo < hi`