Binary Search

The answer is somewhere in this vast, ordered space. Why search from the beginning, when I can ask one question in the middle and instantly eliminate half the possibilities?

In Converging Pointers chapter, we have seen how to exploit the order of a sorted array to solve problems efficiently. Now if you just want to find an element (not a pair), how can you leverage the sorted order to do it in the least number of steps?

Here is a problem to try out. It may not be immediately obvious how this problem is a binary search problem, but once you see it, you will understand the power of binary search. Take 20-30 minutes to try it out.

Problem: Koko Eating Bananas (LeetCode Link) : Koko has n piles of bananas and must eat them all within h hours. She can choose an eating speed of k bananas per hour. Find the minimum integer k (her eating speed) that allows her to finish on time. 💡 HintWhat's the absolute minimum speed koko could possibly have? What's the maximum speed she could have? This defines your range of possible answers. 💡 HintIf you pick speed k and find that koko finishes too slowl (takes more than h hours), what does that tell you about all speeds slower than k?

Binary Search is a foundational algorithm that is used in many problems. Understanding the basic binary search algorithm well will help you to tackle a wide range of problems that involve searching in sorted data structures or even in some unsorted ones.

Standard Binary Search

Binary search works by repeatedly dividing the search interval in half. Here is how it works:

1. Start with left and right pointers at the start and end of the array.
2. Calculate the mid point.
3. If arr[mid] is equal to the target, you're done.
4. If arr[mid] is less than the target, you know the target must be in the right half, so you move left = mid + 1.
5. If arr[mid] is greater than the target, you know the target must be in the left half, so you move right = mid - 1.

The above steps will instantly eliminate half of the search space. You can repeat this process until you either find the target or the search space is empty.

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

    while left <= right:
        mid = (left + right) // 2  # Calculate the middle index
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            left = mid + 1  # Target is in the right half
        else:
            right = mid - 1  # Target is in the left half

    return -1  # Target not found

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the middle index
        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            left = mid + 1; // Target is in the right half
        } else {
            right = mid - 1; // Target is in the left half
        }
    }

    return -1; // Target not found
}

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the middle index
        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            left = mid + 1; // Target is in the right half
        } else {
            right = mid - 1; // Target is in the left half
        }
    }

    return -1; // Target not found
}

Binary Search on the Answer

Once you understand the standard binary search, you can apply the same principles to problems where you need to find an optimal value that satisfies a condition. Here is how it works:

1. Define a search space: First, determine the minimum and maximum possible values for your answer. (For koko, this is a speed from 1 to max(piles)).
2. Define the check function. This function will take a candidate answer and check if it satisfies the condition. For koko, this function will calculate the total hours taken to eat all bananas at a given speed and check if it is less than or equal to h.
3. Binary search: Apply binary search on your range of answers. If check(mid) is true, it means mid is a possible answer, so you try to find an even better one in one half of the range. If it's false, you must search in the other half.

Walkthrough: Solving "Koko Eating Bananas"

Let's apply the Binary Search on the Answer pattern to our challenge.

1. Define the Search Space: We aren't searching the piles array. We are searching for the best speed k.
   • left = 1 (slowest possible speed).
   • right = max(piles) (the fastest Koko would ever need to eat is the size of the largest pile).
2. Binary Search on Speeds: We loop while left <= right. In each iteration, we test a middle speed, k = (left + right) // 2.
3. The check(k) Logic: For a given speed k, we calculate the total hours needed. For each pile p, the time taken is ceil(p / k). We sum these hours up.
4. The Decision:
   • If total_hours <= h: This speed k is valid! Koko can finish. We should save this as a potential answer and try for an even slower speed to see if we can do better. So, we set right = k - 1.
   • If total_hours > h: This speed k is too slow. Koko fails. She must eat faster. So, we set left = k + 1.
5. The loop continues until left and right cross, and the best valid speed we found is our answer.

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    # Define the search space for k (eating speed)
    # The minimum possible speed is 1 (eat at least 1 banana per hour)
    # The maximum possible speed is the maximum number of bananas in any pile
    left, right = 1, max(piles)
    res = right  # Initialize result with a large value

    while left <= right:
        k = (left + right) // 2  # Current eating speed to test
        hours = 0
        # Calculate total hours needed with current speed k
        for p in piles:
            hours += math.ceil(p / k)

        # If Koko can finish within h hours, try a smaller speed
        if hours <= h:
            res = min(res, k)
            right = k - 1
        # If Koko cannot finish within h hours, increase the speed
        else:
            left = k + 1

    return res

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // Define the search space for k (eating speed)
        // The minimum possible speed is 1 (eat at least 1 banana per hour)
        // The maximum possible speed is the maximum number of bananas in any pile
        int left = 1, right = 1;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        int res = right; // Initialize result with a large value

        while (left <= right) {
            int mid = left + (right - left) / 2; // Current eating speed to test
            long hours = 0;
            // Calculate total hours needed with current speed mid
            for (int pile : piles) {
                hours += (pile + mid - 1) / mid; // Equivalent to Math.ceil(pile / mid)
            }

            // Koko can finish the mangoes with current speed mid
            // Save it as a potential result and try to find a smaller speed
            // Koko loves to eat slowly!
            if (hours <= h) {
                res = mid;
                right = mid - 1;
            } 
            // Koko cannot finish with the current speed, go faster
            else {
                left = mid + 1;
            }
        }

        return res;
    }
}

#include <vector>
#include <algorithm>
#include <cmath>

int minEatingSpeed(std::vector<int>& piles, int h) {
    // Define the search space for k (eating speed)
    // The minimum possible speed is 1 (eat at least 1 banana per hour)
    // The maximum possible speed is the maximum number of bananas in any pile
    int left = 1, right = 0;
    for (int pile : piles) {
        right = std::max(right, pile);
    }

    int res = right; // Initialize result with a large value

    while (left <= right) {
        int mid = left + (right - left) / 2; // Current eating speed to test
        long long hours = 0;
        // Calculate total hours needed with current speed mid
        for (int pile : piles) {
            hours += (pile + mid - 1) / mid; // Equivalent to ceil((double)pile / mid)
        }

        // If Koko can finish within h hours, try a smaller speed
        if (hours <= h) {
            res = mid;
            right = mid - 1;
        } 
        // If Koko cannot finish within h hours, increase the speed
        else {
            left = mid + 1;
        }
    }

    return res;
}

Complexity Analysis

• Standard Binary Search:
  • Time Complexity: $O(log N)$ where N is the number of elements in the array.
  • Space Complexity: $O(1)$ for iterative binary search.
• Binary Search on Answer:
  • Time Complexity: $O(N log M)$ where N is the number of piles and M is the range of possible speeds. The log M comes from the binary search, and for each speed we test, we must iterate through all N piles to calculate the hours.
  • Space Complexity: $O(1)$ for iterative binary search.

More Problems & Variations

• Standard Binary Search Problems:
  • Search in Rotated Sorted Array: A variation where you first have to figure out which half of the rotated array is still sorted.
  • Find Minimum in Rotated Sorted Array: Use binary search logic to find the "pivot" point, which will be the minimum element.
  • Time Based Key-Value Store: Use binary search to find the correct timestamp among a sorted list of values for a given key.
• Binary Search on Answer Problems:
  • Capacity To Ship Packages Within D Days: Find the least weight capacity of a ship. The search space is the range of possible capacities.
  • Split Array Largest Sum: Find the minimum largest sum. The search space is the range of possible sum values.