6. Binary Search

What Interviewers Test Here

• Recognising when binary search applies (not just sorted arrays)
• Correct loop invariants (l <= r vs l < r, mid+1 vs mid)
• Binary search on the answer space ("find minimum X such that...")

import bisect

# --- Classic: find target index ---
def binary_search(arr: list[int], target: int) -> int:
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == target:   return mid
        elif arr[mid] < target:  l = mid + 1
        else:                    r = mid - 1
    return -1

# --- First and last position ---
def search_range(nums: list[int], target: int) -> list[int]:
    left  = bisect.bisect_left(nums, target)
    right = bisect.bisect_right(nums, target) - 1
    if left <= right and left < len(nums) and nums[left] == target:
        return [left, right]
    return [-1, -1]

# --- Binary search on answer: minimum capacity to ship in D days ---
def min_capacity(weights: list[int], days: int) -> int:
    def feasible(cap: int) -> bool:
        ships, load = 1, 0
        for w in weights:
            if load + w > cap:
                ships += 1; load = 0
            load += w
        return ships <= days

    l, r = max(weights), sum(weights)
    while l < r:
        mid = (l + r) // 2
        if feasible(mid): r = mid
        else:             l = mid + 1
    return l

---

Conceptual Q&A

Q1: "How do you decide whether to use l <= r or l < r in binary search?"

Walkthrough:

"l <= r — use when you want to check individual elements and can return immediately on a match. The loop exits when l > r (search space exhausted). Common for 'find exact value'.

l < r — use when you're converging to a boundary: the smallest/largest index satisfying a condition. The loop exits when l == r, and you return l (or r) as the answer. Common for lower_bound/upper_bound and 'binary search on answer' problems.

The rule I follow: if I'm looking for an exact match and can return inside the loop → l <= r. If I'm narrowing down to a boundary → l < r, return l after the loop."

---

Q2: "Search in a rotated sorted array: find target."

Walkthrough:

"The array was sorted then rotated, so it looks like [4,5,6,7,0,1,2]. Normal binary search fails because it assumes one sorted half.

Key insight: even after rotation, at least one half of any split is always sorted. I check which half is sorted by comparing arr[l] with arr[mid]:

• If arr[l] <= arr[mid]: left half is sorted → check if target is in [arr[l], arr[mid])
• Otherwise: right half is sorted → check if target is in (arr[mid], arr[r]]

$O(\log n)$ time."

def search_rotated(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        if nums[l] <= nums[mid]:       # left half is sorted
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:                          # right half is sorted
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return -1

---