DSA Masterclass Module 12: Binary Search Patterns

Introduction to Binary Search

Binary Search is the ultimate tool for searching in sorted data. It works by repeatedly halving the search space, achieving an incredible $O(\log n)$ time complexity.

1. Real-World Intuition: The Dictionary

Imagine looking for the word "Java" in a physical dictionary:

You don't start at page 1 (Linear Search).
You open to the middle. If you see "M", you know "J" is in the first half.
You ignore the entire second half and repeat.

2. Curriculum in this Module

Theory & Intuition (Current Page)
Lesson: Standard Binary Search - The core algorithm and dry runs.
Problem: Search in Rotated Array - Handling modified sorting.
Problem: Koko Eating Bananas - Mastering "Search on Answer."
Curated Practice Problems - 10 essential challenges.

3. The Standard Template (Java)

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Final Takeaway

Binary search is not just for searching arrays. It works on any monotonic function (where values are always increasing or always decreasing).