Binary Search & Greedy

Binary search reduces search space by half each step. Greedy algorithms make locally optimal choices. Both are efficient and frequently tested.

Binary Search

Binary search works on sorted data and runs in O(log n) time -- a massive improvement over O(n) linear search.

Standard Binary Search

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # Avoids overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Binary Search Variations

# Find first occurrence (leftmost)
def find_first(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # Keep searching left
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# Search in rotated sorted array
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Instead of searching in a sorted array, you search the answer space -- the range of possible answers.

# Koko eating bananas: minimize eating speed
def min_eating_speed(piles, h):
    import math

    def can_finish(speed):
        return sum(math.ceil(p / speed) for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid  # Try slower
        else:
            left = mid + 1  # Must go faster
    return left

# Split array largest sum: minimize the maximum
def split_array(nums, k):
    def can_split(max_sum):
        count, current = 1, 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
            else:
                current += num
        return count <= k

    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    return left

Pattern Recognition: When the problem asks to "minimize the maximum" or "maximize the minimum," think binary search on the answer space.

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. They work when a problem has the greedy choice property.

Classic Greedy Problems

# Jump game: can you reach the last index?
def can_jump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

# Interval scheduling: maximum non-overlapping intervals
def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    count = 0
    end = float('-inf')
    for start, finish in intervals:
        if start >= end:
            end = finish  # Take this interval
        else:
            count += 1  # Skip (overlap)
    return count

When Greedy Works vs. When It Doesn't

Works (Greedy OK)	Doesn't Work (Need DP)
Activity selection	0/1 Knapsack
Huffman coding	Longest common subsequence
Fractional knapsack	Matrix chain multiplication
Jump game	Edit distance
Interval merging	Coin change (arbitrary denominations)

Interview Tip: If greedy gives the wrong answer on a small example, you likely need dynamic programming instead.

Next, DFS, BFS, and backtracking -- the patterns for exploring all possibilities. :::