LeetCode Patterns ·

🎯 Binary Search

1️⃣ Core Framework

When discussing Binary Search, I frame it as:

What problem pattern it solves
Why binary search reduces complexity
Classic binary search
Lower bound and upper bound
Search insert position
Binary search on answer
Rotated sorted array
Peak finding
Common edge cases
Senior-level explanation

2️⃣ What Problem Are We Solving?

Binary search is used when the search space has a monotonic property.

It is commonly used for:

Searching in sorted arrays
Finding first or last occurrence
Finding insertion position
Searching rotated sorted arrays
Finding minimum in rotated sorted arrays
Finding peak element
Finding smallest valid answer
Finding largest valid answer
Optimizing brute-force search over a numeric range

The core idea is:

Each check eliminates half of the search space.

👉 Interview Answer

Binary search is a search technique used when the search space is sorted or has a monotonic condition.

At each step, we check the middle point and decide which half can be safely discarded.

This reduces the time complexity from O(n) linear search to O(log n).

3️⃣ Why Binary Search Works

Linear Search

A brute-force search scans every element:

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

This takes:

O(n)

Binary Search Optimization

If the array is sorted, we can compare the middle element:

nums[mid] < target → search right half
nums[mid] > target → search left half

Each step cuts the search space in half.

Complexity:

O(log n)

Key Requirement

Binary search requires a way to answer:

Can I discard one side safely?

This usually comes from:

sorted order
monotonic predicate
ordered search space

👉 Interview Answer

Binary search works because the search space can be divided into two parts, and one part can be safely discarded based on the middle check.

In a sorted array, if nums[mid] is smaller than target, everything to the left of mid is also too small.

Therefore, we only need to search the right half.

4️⃣ Classic Binary Search

Problem

Find target in a sorted array.

nums = [1, 3, 5, 7, 9]
target = 7
answer = 3

Code

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Loop Condition

left <= right

Because both left and right are valid candidate positions.

👉 Interview Answer

For classic binary search, I keep an inclusive search range from left to right.

While left is less than or equal to right, I check the middle element.

If it matches the target, I return the index.

If it is smaller than target, I search the right half.

Otherwise, I search the left half.

5️⃣ Binary Search Template Choices

Inclusive Range

left = 0
right = len(nums) - 1

while left <= right:
    mid = left + (right - left) // 2

    if condition:
        return mid
    elif go_right:
        left = mid + 1
    else:
        right = mid - 1

Used for:

find exact target

Half-Open Range

left = 0
right = len(nums)

while left < right:
    mid = left + (right - left) // 2

    if condition:
        right = mid
    else:
        left = mid + 1

Used for:

lower bound
first valid position
search insert position

👉 Interview Answer

I usually use two templates.

For exact search, I use an inclusive range with left <= right.

For boundary search, such as lower bound or first valid position, I use a half-open range with left < right.

The important part is being consistent with the meaning of left and right.

6️⃣ Lower Bound

Meaning

Lower bound finds the first index where:

nums[index] >= target

Code

def lower_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Example

nums = [1, 3, 3, 3, 5, 7]
target = 3

lower_bound = 1

👉 Interview Answer

Lower bound returns the first index where nums[index] is greater than or equal to target.

If nums[mid] is greater than or equal to target, mid may be the answer, so I keep it by moving right to mid.

Otherwise, I move left to mid + 1.

7️⃣ Upper Bound

Meaning

Upper bound finds the first index where:

nums[index] > target

Code

def upper_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Example

nums = [1, 3, 3, 3, 5, 7]
target = 3

upper_bound = 4

👉 Interview Answer

Upper bound returns the first index where nums[index] is greater than target.

If nums[mid] is greater than target, it could be the answer, so I move right to mid.

Otherwise, nums[mid] is still too small or equal to target, so I move left to mid + 1.

8️⃣ First and Last Position of Target

Problem

Find the first and last index of target in a sorted array.

nums = [5, 7, 7, 8, 8, 10]
target = 8
answer = [3, 4]

Code

def search_range(nums, target):
    first = lower_bound(nums, target)

    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    last = upper_bound(nums, target) - 1

    return [first, last]

Why It Works

first occurrence = lower_bound(target)
last occurrence = upper_bound(target) - 1

👉 Interview Answer

To find the first and last position of a target, I use lower bound and upper bound.

The first position is the first index greater than or equal to target.

The last position is the first index greater than target minus one.

9️⃣ Search Insert Position

Problem

Return the index where target should be inserted in a sorted array.

nums = [1, 3, 5, 6]
target = 5
answer = 2

target = 2
answer = 1

target = 7
answer = 4

Code

def search_insert(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Same As Lower Bound

search insert position = lower_bound(target)

👉 Interview Answer

Search insert position is essentially lower bound.

We need the first index where the value is greater than or equal to target.

If target already exists, that is its index.

If not, that is the correct insertion position.

🔟 Binary Search on Answer

Core Idea

Sometimes the array itself is not sorted, but the answer space is monotonic.

We search over possible answers.

Can we do it with x?

If yes, then maybe a smaller or larger answer is possible depending on the problem.

Common Problems

Koko Eating Bananas
Capacity to Ship Packages Within D Days
Split Array Largest Sum
Minimum eating speed
Minimum time to finish jobs
Smallest divisor under threshold

Pattern

Define search range.
Define feasible(x).
Binary search for the smallest x that satisfies feasible(x).

👉 Interview Answer

Binary search can be applied not only to sorted arrays, but also to a monotonic answer space.

If we can write a feasibility function where answers become valid after some threshold, then we can binary search for the smallest valid answer or largest valid answer.

1️⃣1️⃣ Binary Search on Answer Template

Find Smallest Valid Answer

def binary_search_answer(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

Meaning

false false false true true true
                 ^
              answer

We want the first true.

Find Largest Valid Answer

def binary_search_largest(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if feasible(mid):
            left = mid
        else:
            right = mid - 1

    return left

Meaning

true true true false false false
             ^
          answer

We want the last true.

👉 Interview Answer

For binary search on answer, I first define the answer range.

Then I write a feasibility function.

If I am looking for the smallest valid answer, I move right to mid when mid is feasible.

If I am looking for the largest valid answer, I move left to mid when mid is feasible.

1️⃣2️⃣ Koko Eating Bananas

Problem

Find the minimum eating speed so Koko can finish all piles within h hours.

Monotonic Property

If speed k works:

any speed larger than k also works

So the validity pattern is:

false false false true true true

We need the first true.

Code

import math

def min_eating_speed(piles, h):
    left = 1
    right = max(piles)

    def feasible(speed):
        hours = 0

        for pile in piles:
            hours += math.ceil(pile / speed)

        return hours <= h

    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

Avoid Floating Point

hours += (pile + speed - 1) // speed

👉 Interview Answer

Koko Eating Bananas is binary search on answer.

The answer is the eating speed.

If a certain speed can finish within h hours, any larger speed also works.

So I binary search for the smallest feasible speed.

1️⃣3️⃣ Capacity to Ship Packages Within D Days

Problem

Find the minimum ship capacity to ship all packages within D days.

Search Range

Minimum capacity:

max(weights)

Because the ship must carry the heaviest package.

Maximum capacity:

sum(weights)

Because shipping everything in one day always works.

Code

def ship_within_days(weights, days):
    left = max(weights)
    right = sum(weights)

    def feasible(capacity):
        used_days = 1
        current = 0

        for weight in weights:
            if current + weight > capacity:
                used_days += 1
                current = 0

            current += weight

        return used_days <= days

    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

👉 Interview Answer

The search space is the possible ship capacity.

If a capacity works, any larger capacity also works.

So the predicate is monotonic.

I binary search for the minimum feasible capacity.

1️⃣4️⃣ Rotated Sorted Array

Problem

Search target in a rotated sorted array.

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
answer = 4

Key Insight

At every step, at least one half is sorted.

left half sorted
or
right half sorted

Use the sorted half to decide whether target is inside.

Code

def search_rotated(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            # left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

👉 Interview Answer

In a rotated sorted array, one side of the current range is always sorted.

I first determine whether the left half or right half is sorted.

Then I check whether the target lies inside that sorted half.

If it does, I search that half.

Otherwise, I search the other half.

1️⃣5️⃣ Find Minimum in Rotated Sorted Array

Problem

Find the minimum element in a rotated sorted array.

nums = [4, 5, 6, 7, 0, 1, 2]
answer = 0

Key Insight

Compare nums[mid] with nums[right].

nums[mid] > nums[right]
→ minimum is on the right side

nums[mid] <= nums[right]
→ minimum is at mid or on the left side

Code

def find_min(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

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

    return nums[left]

👉 Interview Answer

To find the minimum in a rotated sorted array, I compare nums[mid] with nums[right].

If nums[mid] is greater than nums[right], the minimum must be to the right of mid.

Otherwise, mid could be the minimum, so I keep mid by moving right to mid.

1️⃣6️⃣ Peak Element

Problem

Find an index i such that:

nums[i] > nums[i - 1]
and
nums[i] > nums[i + 1]

Key Insight

Compare nums[mid] with nums[mid + 1].

nums[mid] < nums[mid + 1]
→ we are going uphill, peak exists on the right

nums[mid] > nums[mid + 1]
→ we are going downhill, peak exists at mid or on the left

Code

def find_peak_element(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

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

    return left

👉 Interview Answer

For peak element, I compare nums[mid] and nums[mid + 1].

If nums[mid] is smaller than nums[mid + 1], then the slope is increasing, so a peak must exist on the right.

Otherwise, a peak exists at mid or on the left.

This allows binary search even though the array is not globally sorted.

1️⃣7️⃣ First Bad Version

Problem Pattern

Find the first version where a condition becomes true.

good good good bad bad bad
               ^
          first bad

Code

def first_bad_version(n):
    left = 1
    right = n

    while left < right:
        mid = left + (right - left) // 2

        if isBadVersion(mid):
            right = mid
        else:
            left = mid + 1

    return left

Pattern

This is lower bound over a boolean array.

false false false true true true

👉 Interview Answer

First Bad Version is a boundary binary search problem.

The predicate changes from false to true.

I search for the first true.

When mid is bad, I keep mid by moving right to mid.

Otherwise, I move left to mid + 1.

1️⃣8️⃣ Binary Search Over Boolean Predicate

General Pattern

Many binary search problems are really about finding a boundary:

false false false true true true

or:

true true true false false false

First True

def first_true(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if predicate(mid):
            right = mid
        else:
            left = mid + 1

    return left

Last True

def last_true(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if predicate(mid):
            left = mid
        else:
            right = mid - 1

    return left

👉 Interview Answer

At a deeper level, many binary search problems are boundary search problems over a monotonic boolean predicate.

Instead of thinking only about sorted arrays, I think about whether the predicate forms false-then-true or true-then-false.

Then I choose the correct template for first true or last true.

1️⃣9️⃣ Common Edge Cases

Empty Array

nums = []

One Element

nums = [5]

Target Smaller Than All Elements

target < nums[0]

Target Larger Than All Elements

target > nums[-1]

Duplicates

Duplicates affect:

first occurrence
last occurrence
rotated array with duplicates

Infinite Loop

Usually caused by:

mid not excluded correctly
left = mid
right = mid

without using upper mid when needed.

👉 Interview Answer

The main edge cases are empty input, single-element arrays, targets outside the range, duplicates, and infinite loops caused by incorrect pointer updates.

I avoid these issues by clearly defining whether my search range is inclusive or half-open.

2️⃣0️⃣ Complexity Analysis

Time Complexity

Classic binary search:

O(log n)

Because the search space halves each iteration.

Space Complexity

Iterative implementation:

O(1)

Recursive implementation:

O(log n)

because of call stack.

Binary Search on Answer

O(log range * cost(feasible))

Example:

Koko Eating Bananas:
O(n log max(piles))

👉 Interview Answer

Standard binary search takes O(log n) time and O(1) space when implemented iteratively.

For binary search on answer, the complexity is O(log range multiplied by the cost of the feasibility check).

So I always analyze both the number of binary search iterations and the cost of each check.

2️⃣1️⃣ Common Mistakes

Mistake 1: Not Defining Search Range Clearly

Is right inclusive?
Is right exclusive?

Mistake 2: Wrong Loop Condition

left <= right
vs
left < right

Mistake 3: Off-by-One Updates

right = mid
right = mid - 1
left = mid
left = mid + 1

Mistake 4: Infinite Loop

For last true search, use upper mid:

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

Mistake 5: Missing Monotonicity

Binary search only works if the predicate is monotonic.

👉 Interview Answer

The most common binary search bugs come from unclear boundary definitions.

Before coding, I define whether the range is inclusive or half-open, what left and right mean, and whether I am looking for first true, last true, or exact target.

This avoids most off-by-one and infinite-loop issues.

2️⃣2️⃣ Standard Templates

Exact Search Template

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Lower Bound Template

def lower_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Upper Bound Template

def upper_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

First True Template

def first_true(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if predicate(mid):
            right = mid
        else:
            left = mid + 1

    return left

Last True Template

def last_true(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if predicate(mid):
            left = mid
        else:
            right = mid - 1

    return left

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Binary search is a search technique used when the search space is sorted or when there is a monotonic predicate.

The core idea is to check the middle of the search space and safely discard one half.

This reduces the search complexity from O(n) to O(log n).

In the classic sorted-array case, if nums[mid] is smaller than the target, then everything to the left of mid is also too small, so we search the right half.

If nums[mid] is greater than the target, we search the left half.

For exact target search, I usually use an inclusive range with left <= right.

For boundary search, such as lower bound, upper bound, search insert position, or first bad version, I prefer a half-open or first-true template.

At a deeper level, many binary search problems are not really about arrays. They are about finding a boundary in a monotonic boolean space.

For example, in binary search on answer, we define a feasibility function. If feasible(x) changes from false to true as x increases, then we can binary search for the smallest valid x.

This applies to problems like Koko Eating Bananas, Capacity to Ship Packages Within D Days, Split Array Largest Sum, and similar optimization problems.

Binary search also applies to rotated sorted arrays, where one half of the current range is always sorted, and to peak finding, where the local slope tells us which side must contain a peak.

The main risks are off-by-one errors, unclear boundary definitions, wrong loop conditions, infinite loops, and applying binary search when the predicate is not monotonic.

At a senior level, I would always explain: what the search space is, what the monotonic property is, what condition eliminates half the space, and what invariant left and right maintain.

⭐ Final Insight

Binary Search 的核心不是“数组有序就找 mid”。

它的核心是找到一个 monotonic search space。

Senior-level 的重点是：

search space 是什么， predicate 是否单调，要找 first true、last true，还是 exact target，以及每次为什么可以安全丢掉一半。

能讲清楚这些， Binary Search 就不只是一个模板，而是一种把问题转化成 boundary finding 的思维方式。

中文部分

🎯 Binary Search

1️⃣ 核心框架

讨论 Binary Search 时，我通常从：

它解决什么问题
为什么 binary search 可以降低复杂度
经典 binary search
Lower bound 和 upper bound
Search insert position
Binary search on answer
Rotated sorted array
Peak finding
常见 edge cases
高级工程师解释方式

2️⃣ 要解决什么问题？

Binary search 用于搜索空间具有 单调性 的问题。

它常用于：

Searching in sorted arrays
Finding first or last occurrence
Finding insertion position
Searching rotated sorted arrays
Finding minimum in rotated sorted arrays
Finding peak element
Finding smallest valid answer
Finding largest valid answer
Optimizing brute-force search over a numeric range

核心思想是：

每次检查中间点，
然后安全丢掉一半搜索空间。

👉 面试回答

Binary search 是一种用于 sorted search space 或 monotonic condition 的搜索技巧。

每一步检查 middle point，然后判断哪一半可以被安全排除。

这样可以把 O(n) 的线性搜索优化成 O(log n)。

3️⃣ 为什么 Binary Search 有效？

Linear Search

暴力搜索需要扫描每个元素：

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

复杂度是：

O(n)

Binary Search 优化

如果数组有序，可以比较中间元素：

nums[mid] < target → 搜索右半边
nums[mid] > target → 搜索左半边

每次都砍掉一半搜索空间。

复杂度：

O(log n)

关键条件

Binary search 的前提是能回答：

我能不能安全丢掉一边？

这通常来自：

sorted order
monotonic predicate
ordered search space

👉 面试回答

Binary search 有效，是因为搜索空间可以被分成两部分，并且可以根据 mid 的结果安全排除其中一部分。

在 sorted array 中，如果 nums[mid] 小于 target，那么 mid 左边的元素也都太小。

所以只需要搜索右半边。

4️⃣ 经典 Binary Search

Problem

在 sorted array 中查找 target。

nums = [1, 3, 5, 7, 9]
target = 7
answer = 3

Code

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Loop Condition

left <= right

因为 left 和 right 都是有效候选位置。

👉 面试回答

对经典 binary search，我使用 inclusive search range，也就是 left 到 right 都是候选位置。

当 left <= right 时，检查中间元素。

如果等于 target，返回 index。

如果小于 target，搜索右半边。

否则搜索左半边。

5️⃣ Binary Search 模板选择

Inclusive Range

left = 0
right = len(nums) - 1

while left <= right:
    mid = left + (right - left) // 2

    if condition:
        return mid
    elif go_right:
        left = mid + 1
    else:
        right = mid - 1

用于：

find exact target

Half-Open Range

left = 0
right = len(nums)

while left < right:
    mid = left + (right - left) // 2

    if condition:
        right = mid
    else:
        left = mid + 1

用于：

lower bound
first valid position
search insert position

👉 面试回答

我通常使用两种模板。

如果是 exact search，我用 inclusive range 和 left <= right。

如果是 boundary search，比如 lower bound 或 first valid position，我用 half-open range 和 left < right。

关键是始终保持 left 和 right 含义一致。

6️⃣ Lower Bound

Meaning

Lower bound 找第一个满足：

nums[index] >= target

的位置。

Code

def lower_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Example

nums = [1, 3, 3, 3, 5, 7]
target = 3

lower_bound = 1

👉 面试回答

Lower bound 返回第一个大于等于 target 的 index。

如果 nums[mid] >= target， mid 可能是答案，所以保留 mid，令 right = mid。

否则，mid 太小，令 left = mid + 1。

7️⃣ Upper Bound

Meaning

Upper bound 找第一个满足：

nums[index] > target

的位置。

Code

def upper_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Example

nums = [1, 3, 3, 3, 5, 7]
target = 3

upper_bound = 4

👉 面试回答

Upper bound 返回第一个大于 target 的 index。

如果 nums[mid] > target， mid 可能是答案，所以 right = mid。

否则 nums[mid] 仍然小于或等于 target，所以 left = mid + 1。

8️⃣ First and Last Position of Target

Problem

在 sorted array 中找 target 的第一个和最后一个位置。

nums = [5, 7, 7, 8, 8, 10]
target = 8
answer = [3, 4]

Code

def search_range(nums, target):
    first = lower_bound(nums, target)

    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    last = upper_bound(nums, target) - 1

    return [first, last]

为什么正确？

first occurrence = lower_bound(target)
last occurrence = upper_bound(target) - 1

👉 面试回答

找 target 的第一个和最后一个位置，可以用 lower bound 和 upper bound。

第一个位置是第一个大于等于 target 的位置。

最后一个位置是第一个大于 target 的位置减一。

9️⃣ Search Insert Position

Problem

返回 target 应该插入 sorted array 的位置。

nums = [1, 3, 5, 6]
target = 5
answer = 2

target = 2
answer = 1

target = 7
answer = 4

Code

def search_insert(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

本质

search insert position = lower_bound(target)

👉 面试回答

Search insert position 本质上就是 lower bound。

我们要找第一个大于等于 target 的 index。

如果 target 存在，这就是它的位置。

如果不存在，这就是正确插入位置。

🔟 Binary Search on Answer

核心思想

有时候 array 本身不是 sorted，但是答案空间具有单调性。

我们搜索的是可能的答案。

Can we do it with x?

如果 x 可以，那么更大或更小的 x 是否也可以，取决于题目。

常见题

Koko Eating Bananas
Capacity to Ship Packages Within D Days
Split Array Largest Sum
Minimum eating speed
Minimum time to finish jobs
Smallest divisor under threshold

Pattern

Define search range.
Define feasible(x).
Binary search for the smallest x that satisfies feasible(x).

👉 面试回答

Binary search 不仅可以用于 sorted array，也可以用于 monotonic answer space。

如果我们能写出一个 feasibility function，并且答案在某个 threshold 后从 invalid 变成 valid，那就可以 binary search 找 smallest valid answer 或 largest valid answer。

1️⃣1️⃣ Binary Search on Answer 模板

Find Smallest Valid Answer

def binary_search_answer(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

Meaning

false false false true true true
                 ^
              answer

我们找 first true。

Find Largest Valid Answer

def binary_search_largest(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if feasible(mid):
            left = mid
        else:
            right = mid - 1

    return left

Meaning

true true true false false false
             ^
          answer

我们找 last true。

👉 面试回答

对 binary search on answer，我会先定义答案范围。

然后写 feasible function。

如果要找 smallest valid answer，当 mid feasible 时，令 right = mid。

如果要找 largest valid answer，当 mid feasible 时，令 left = mid。

1️⃣2️⃣ Koko Eating Bananas

Problem

找到最小 eating speed，使 Koko 能在 h 小时内吃完所有香蕉。

Monotonic Property

如果 speed k 可以：

任何比 k 更大的 speed 也可以

所以 validity pattern 是：

false false false true true true

我们要找 first true。

Code

def min_eating_speed(piles, h):
    left = 1
    right = max(piles)

    def feasible(speed):
        hours = 0

        for pile in piles:
            hours += (pile + speed - 1) // speed

        return hours <= h

    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

👉 面试回答

Koko Eating Bananas 是 binary search on answer。

答案是 eating speed。

如果某个 speed 能在 h 小时内完成，那么更大的 speed 一定也能完成。

所以我 binary search 找最小 feasible speed。

1️⃣3️⃣ Capacity to Ship Packages Within D Days

Problem

找到最小 ship capacity，使所有 packages 能在 D 天内运完。

Search Range

最小 capacity：

max(weights)

因为船必须能装下最重的 package。

最大 capacity：

sum(weights)

因为一天运完所有 package 一定可以。

Code

def ship_within_days(weights, days):
    left = max(weights)
    right = sum(weights)

    def feasible(capacity):
        used_days = 1
        current = 0

        for weight in weights:
            if current + weight > capacity:
                used_days += 1
                current = 0

            current += weight

        return used_days <= days

    while left < right:
        mid = left + (right - left) // 2

        if feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

👉 面试回答

这个题的 search space 是可能的 ship capacity。

如果某个 capacity 可以完成，更大的 capacity 也一定可以。

所以 predicate 是 monotonic。

我 binary search 找 minimum feasible capacity。

1️⃣4️⃣ Rotated Sorted Array

Problem

在 rotated sorted array 中搜索 target。

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
answer = 4

Key Insight

每一步至少有一半是 sorted。

left half sorted
or
right half sorted

用 sorted half 判断 target 是否在里面。

Code

def search_rotated(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            # left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

👉 面试回答

在 rotated sorted array 中，当前范围内一定至少有一半是 sorted。

我先判断左半边还是右半边有序。

然后判断 target 是否落在有序的一半里。

如果是，就搜索那一半。

否则搜索另一半。

1️⃣5️⃣ Find Minimum in Rotated Sorted Array

Problem

找到 rotated sorted array 中的最小元素。

nums = [4, 5, 6, 7, 0, 1, 2]
answer = 0

Key Insight

比较 nums[mid] 和 nums[right]。

nums[mid] > nums[right]
→ minimum 在右半边

nums[mid] <= nums[right]
→ minimum 在 mid 或左半边

Code

def find_min(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

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

    return nums[left]

👉 面试回答

找 rotated sorted array 的 minimum，我会比较 nums[mid] 和 nums[right]。

如果 nums[mid] > nums[right]，说明 minimum 一定在 mid 右边。

否则 mid 可能就是 minimum，所以保留 mid，令 right = mid。

1️⃣6️⃣ Peak Element

Problem

找一个 index i，满足：

nums[i] > nums[i - 1]
and
nums[i] > nums[i + 1]

Key Insight

比较 nums[mid] 和 nums[mid + 1]。

nums[mid] < nums[mid + 1]
→ 正在上坡，右边一定有 peak

nums[mid] > nums[mid + 1]
→ 正在下坡，mid 或左边一定有 peak

Code

def find_peak_element(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

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

    return left

👉 面试回答

对 peak element，我比较 nums[mid] 和 nums[mid + 1]。

如果 nums[mid] < nums[mid + 1]，说明右边方向是上坡，因此右边一定存在 peak。

否则 mid 或左边一定存在 peak。

所以即使数组不是全局 sorted，也可以使用 binary search。

1️⃣7️⃣ First Bad Version

Problem Pattern

找第一个 condition 变成 true 的位置。

good good good bad bad bad
               ^
          first bad

Code

def first_bad_version(n):
    left = 1
    right = n

    while left < right:
        mid = left + (right - left) // 2

        if isBadVersion(mid):
            right = mid
        else:
            left = mid + 1

    return left

Pattern

这是 boolean array 上的 lower bound：

false false false true true true

👉 面试回答

First Bad Version 是 boundary binary search。

Predicate 从 false 变成 true。

我们要找 first true。

当 mid 是 bad version 时，mid 可能就是答案，所以 right = mid。

否则 left = mid + 1。

1️⃣8️⃣ Binary Search Over Boolean Predicate

General Pattern

很多 binary search 本质是在找 boundary：

false false false true true true

或者：

true true true false false false

First True

def first_true(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if predicate(mid):
            right = mid
        else:
            left = mid + 1

    return left

Last True

def last_true(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if predicate(mid):
            left = mid
        else:
            right = mid - 1

    return left

👉 面试回答

更深一层看，很多 binary search 其实是在 monotonic boolean predicate 上找 boundary。

不要只想着 sorted array。

我会先判断 predicate 是 false-then-true，还是 true-then-false。

然后选择 first true 或 last true 的模板。

1️⃣9️⃣ 常见 Edge Cases

Empty Array

nums = []

One Element

nums = [5]

Target Smaller Than All Elements

target < nums[0]

Target Larger Than All Elements

target > nums[-1]

Duplicates

Duplicates 会影响：

first occurrence
last occurrence
rotated array with duplicates

Infinite Loop

通常是因为：

mid 没有被正确排除
left = mid
right = mid

但没有配合 upper mid。

👉 面试回答

常见 edge cases 包括 empty input、 single element、 target 在数组范围外、 duplicates、以及 pointer update 错误导致 infinite loop。

我会通过清楚定义 search range 是 inclusive 还是 half-open 来避免这些问题。

2️⃣0️⃣ Complexity Analysis

Time Complexity

经典 binary search：

O(log n)

因为搜索空间每次减半。

Space Complexity

Iterative implementation：

O(1)

Recursive implementation：

O(log n)

因为 call stack。

Binary Search on Answer

O(log range * cost(feasible))

Example：

Koko Eating Bananas:
O(n log max(piles))

👉 面试回答

标准 binary search 是 O(log n) time， iterative 写法是 O(1) space。

对 binary search on answer，复杂度是 O(log range * feasibility check cost)。

所以需要同时分析 binary search 的迭代次数，和每次 feasible function 的成本。

2️⃣1️⃣ 常见错误

Mistake 1: Search Range 没定义清楚

right 是 inclusive 还是 exclusive？

Mistake 2: Loop Condition 错误

left <= right
vs
left < right

Mistake 3: Off-by-One Updates

right = mid
right = mid - 1
left = mid
left = mid + 1

Mistake 4: Infinite Loop

找 last true 时，用 upper mid：

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

Mistake 5: 没有 Monotonicity

Binary search 只有在 predicate 单调时才成立。

👉 面试回答

Binary search 最常见的 bug 来自 boundary 定义不清。

写代码前，我会先定义： range 是 inclusive 还是 half-open， left 和 right 分别代表什么，要找 first true、last true，还是 exact target。

这样可以避免大部分 off-by-one 和 infinite loop 问题。

2️⃣2️⃣ 标准模板

Exact Search Template

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Lower Bound Template

def lower_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

Upper Bound Template

def upper_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:
        mid = left + (right - left) // 2

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

    return left

First True Template

def first_true(left, right):
    while left < right:
        mid = left + (right - left) // 2

        if predicate(mid):
            right = mid
        else:
            left = mid + 1

    return left

Last True Template

def last_true(left, right):
    while left < right:
        mid = left + (right - left + 1) // 2

        if predicate(mid):
            left = mid
        else:
            right = mid - 1

    return left

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Binary search 是一种用于 sorted search space 或 monotonic predicate 的搜索技巧。

它的核心思想是检查 search space 的中间点，然后根据结果安全丢掉一半搜索空间。

因此它可以把 O(n) 的搜索优化成 O(log n)。

在经典 sorted array 场景中，如果 nums[mid] 小于 target，那么 mid 左边的元素也一定小于 target，所以我们搜索右半边。

如果 nums[mid] 大于 target，就搜索左半边。

对 exact target search，我通常使用 inclusive range，也就是 left <= right。

对 boundary search，比如 lower bound、upper bound、search insert position、或 first bad version，我更倾向使用 half-open 或 first-true 模板。

更深一层看，很多 binary search 问题并不是在搜索数组，而是在 monotonic boolean space 上找 boundary。

比如 binary search on answer，我们会定义一个 feasibility function。如果 feasible(x) 随着 x 增大从 false 变成 true，就可以 binary search 找 smallest valid x。

这适用于 Koko Eating Bananas、 Capacity to Ship Packages Within D Days、 Split Array Largest Sum 等优化问题。

Binary search 也可以用于 rotated sorted array。在这种题中，当前区间至少有一半是 sorted，可以通过 sorted half 判断 target 是否在其中。

它也可以用于 peak finding。虽然数组不是全局 sorted，但 local slope 可以告诉我们哪一侧一定存在 peak。

主要风险是 off-by-one、 boundary 定义不清、 loop condition 错误、 infinite loop，以及在 predicate 不单调时误用 binary search。

高级工程师解释时，我会重点说明： search space 是什么， monotonic property 是什么，每次为什么能排除一半，以及 left 和 right 维护的 invariant 是什么。

⭐ Final Insight

Binary Search 的核心不是“找中间点”。

它的核心是找到一个 monotonic boundary。

Senior-level 的重点是：

search space 是什么， predicate 是否单调，要找 first true、last true，还是 exact target，以及为什么每一步可以安全丢掉一半。

能讲清楚这些， Binary Search 就是一种强大的 boundary-finding 思维模型。