Binary Search

1. Introduction: The Dictionary Trick

If you need to find the word "Mango" in a physical dictionary, you don't start at page 1 and read every word until you hit "Mango" ($O(N)$). Instead, you open the book roughly in the middle. You land on the letter "P". Since "M" comes before "P", you completely ignore the second half of the dictionary. You then open the middle of the left half. You repeat this until you find "Mango".

This is Binary Search. It is a Divide and Conquer algorithm that searches a sorted array by repeatedly dividing the search interval in half. While a linear search of 1 billion items takes 1 billion operations, Binary Search takes at most $\approx 30$ operations ($O(\log N)$). It is one of the most powerful and fundamental algorithms in computer science.

2. Core Concept: The Search Space

To write a Binary Search, you need three things:

1. A Sorted Search Space: Usually an array, but sometimes a mathematical range of numbers (e.g., from 1 to $N$).
2. Left and Right Pointers: These define the boundaries of your current search space.
3. A Condition: A way to evaluate the middle element to determine whether you should discard the left half or the right half.

The Math: At each step, the size of the search space $N$ is halved: $N \rightarrow N/2 \rightarrow N/4 \rightarrow \dots \rightarrow 1$. The number of steps $k$ it takes to reach 1 is solved by the equation $\frac{N}{2^k} = 1 \implies 2^k = N \implies k = \log_2 N$.

3. Beginner Code Example: The Classic Template

Problem Statement: Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Iterative Approach (Recommended)

public class BinarySearchIterative {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        // <= is crucial! If left and right point to the same element,
        // we still need to check if that element is the target!
        while (left <= right) {
            // Calculate mid safely to prevent integer overflow
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid; // Found it!
            } else if (nums[mid] < target) {
                // Target is larger, it must be in the right half
                left = mid + 1;
            } else {
                // Target is smaller, it must be in the left half
                right = mid - 1;
            }
        }
        
        return -1; // Not found
    }
}

Complexity Analysis:

• Time Complexity: $O(\log N)$.
• Space Complexity: $O(1)$.

Recursive Approach

public class BinarySearchRecursive {
    public static int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
    
    private static int binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) return -1; // Base case: not found
        
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, right);
        } else {
            return binarySearch(nums, target, left, mid - 1);
        }
    }
}

Note: The recursive approach uses $O(\log N)$ auxiliary space for the call stack, which is why the iterative approach is almost always preferred in production and interviews.

4. Intermediate Code Example: First and Last Position (Bounds)

Problem Statement: (LeetCode 34) Find First and Last Position of Element in Sorted Array. Given an array sorted in non-decreasing order, find the starting and ending position of a given target value.

Because the array has duplicates, finding the target once isn't enough. If we find the target, to get the "first" position, we don't return immediately—we keep searching the left half to see if there's an earlier occurrence.

public class BinarySearchBounds {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findBound(nums, target, true);  // Find first occurrence
        result[1] = findBound(nums, target, false); // Find last occurrence
        return result;
    }
    
    private static int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0;
        int right = nums.length - 1;
        int boundIndex = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                boundIndex = mid; // Record the index
                if (isFirst) {
                    right = mid - 1; // Keep looking left
                } else {
                    left = mid + 1;  // Keep looking right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return boundIndex;
    }
}

5. Advanced Code Example: Search in Rotated Sorted Array

Problem Statement: (LeetCode 33) You are given an integer array nums sorted in ascending order (with distinct values), which is then rotated at an unknown pivot (e.g., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the index of target in $O(\log N)$ time.

The Insight: If you cut a rotated array in half, at least one half will always be perfectly sorted. We can check which half is sorted, and then easily check if the target falls within the boundaries of that sorted half!

public class RotatedBinarySearch {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) return mid;
            
            // Determine which half is strictly sorted
            if (nums[left] <= nums[mid]) {
                // The LEFT half is sorted
                // Is the target mathematically inside this sorted left half?
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // Yes, discard right half
                } else {
                    left = mid + 1;  // No, discard left half
                }
            } else {
                // The RIGHT half is sorted
                // Is the target mathematically inside this sorted right half?
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;  // Yes, discard left half
                } else {
                    right = mid - 1; // No, discard right half
                }
            }
        }
        
        return -1;
    }
}

Complexity Analysis:

• Time Complexity: $O(\log N)$. We still discard half the array at every step.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Integer Overflow on mid Calculation

   • The Mistake: int mid = (left + right) / 2;
   • Why it's wrong: If left and right are both very large numbers (e.g., near Integer.MAX_VALUE), their sum will overflow the 32-bit limit, wrapping around to a negative number. This throws an ArrayIndexOutOfBoundsException.
   • The Fix: int mid = left + (right - left) / 2;

2. Infinite Loops (while (left < right))

   • The Mistake: Depending on how you assign left and right, using < instead of <= can cause the loop to end prematurely, missing the last element, or get stuck if you use left = mid;.
   • The Fix: The standard while (left <= right) with left = mid + 1 and right = mid - 1 is foolproof and guarantees the loop will terminate.

3. Applying Binary Search to Unsorted Data

   • The Mistake: The problem doesn't say "sorted", but you use Binary Search anyway.
   • Why it's wrong: Discarding half the array relies entirely on the mathematical guarantee that all elements to the left are smaller, and all to the right are larger. If it's unsorted, this guarantee is broken.

7. Interview Q&A

Q1: What is "Binary Search on Answer" (or Parametric Search)? Answer: Sometimes the array isn't what's sorted—the answers are sorted! For example, "What is the minimum speed Koko can eat bananas to finish in H hours?" Eating slower takes more hours, eating faster takes fewer hours. Because there is a monotonic relationship, we can Binary Search the speed (from 1 to Max), checking if a speed is valid. (LeetCode 875).

Q2: How do you perform a Binary Search on a 2D Matrix? Answer: If the matrix is completely sorted (the end of row 1 connects to the start of row 2), you can conceptually flatten it into a 1D array of size M * N. To access elements, map the 1D mid index back to 2D coordinates using row = mid / cols and col = mid % cols.

Q3: Can Binary Search be used to find a peak element? Answer: Yes! (LeetCode 162). Even though the array isn't fully sorted, you can find a local peak. If arr[mid] < arr[mid+1], the array is sloping upward to the right, so a peak MUST exist to the right. We can safely discard the left half. This is binary searching based on the derivative (slope)!

Q4: Is Binary Search faster than a HashSet? Answer: A HashSet.contains() takes $O(1)$ average time, which is technically faster than $O(\log N)$. However, a HashSet requires $O(N)$ extra memory, and has high constant-factor overhead due to hashing and object allocation. Binary Search operates in-place ($O(1)$ memory) and uses pure array lookups, making it incredibly cache-efficient and often faster in real-world micro-benchmarks for moderately sized data.

8. Practice Problems

1. Binary Search (LeetCode 704)
   • Goal: Master the standard template.
2. Search Insert Position (LeetCode 35)
   • Hint: If target is not found, what does the left pointer represent when the loop breaks? (It represents the exact insertion index!).
3. Koko Eating Bananas (LeetCode 875)
   • Hint: A classic "Binary Search on Answer" problem.

9. Summary

• Requirement: Data must be sorted, or exhibit some monotonic property (like a consistent slope).
• The Core Formula: $O(\log N)$ is achieved by safely calculating mid = left + (right - left) / 2 and updating bounds to mid + 1 or mid - 1.
• Advanced Variants: Rotated arrays are solved by finding which half is strictly sorted. Range bounds are solved by not stopping when the target is found, but aggressively continuing the search in one direction.
• Parametric Search: Binary search isn't just for finding indices; it's heavily used to find optimal integer answers in optimization problems.