Advanced Binary Search

Advanced Binary Search: Finding Treasures in Special Grids

The Treasure Hunter’s Secret Technique

Imagine you’re a treasure hunter with a magical compass. Instead of walking through every room in a castle, your compass tells you: “Go left!” or “Go right!” — cutting your search in half each time. That’s Binary Search!

But today, we’re going on two EPIC adventures:

1. The Magic Library — Finding a book in a special grid
2. The Two Rivers — Finding the perfect middle point

Part 1: Search in 2D Matrix

The Magic Library Story

Picture a library where books are arranged in a special way:

• Each shelf (row) has books sorted from small to big (left to right)
• The first book on each shelf is bigger than the last book on the shelf above

Shelf 1:  [ 1,  3,  5,  7]
Shelf 2:  [10, 11, 16, 20]
Shelf 3:  [23, 30, 34, 60]

Question: Is book #16 in this library?

Why This Grid is MAGICAL

Look carefully! If you read ALL numbers left-to-right, top-to-bottom:

1 → 3 → 5 → 7 → 10 → 11 → 16 → 20 → 23 → 30 → 34 → 60

It’s already sorted! The 2D grid is secretly a 1D sorted list!

The Two-Step Dance

Step 1: Find the Right Shelf Use binary search on the first column to find which row might have our book.

Step 2: Search That Shelf Use binary search on that row to find the exact book.

The Smart Single-Search Method

Even smarter! Treat the whole grid as ONE sorted list:

public boolean searchMatrix(int[][] matrix,
                            int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int left = 0;
    int right = rows * cols - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        // Magic formula to find row & col!
        int row = mid / cols;
        int col = mid % cols;
        int value = matrix[row][col];

        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

The Magic Formula Explained

If our grid has 4 columns, and we want position 6:

• Row = 6 ÷ 4 = 1 (second row, remember we start at 0!)
• Column = 6 % 4 = 2 (third column)

Position 6 → matrix[1][2] = 16 ✓

graph TD
    A["2D Grid 3x4"] --> B["Treat as 1D: 12 items"]
    B --> C["Binary Search"]
    C --> D["mid = 5"]
    D --> E["row = 5÷4 = 1"]
    D --> F["col = 5%4 = 1"]
    E --> G["matrix 1 1 = 11"]
    F --> G

Walk-Through Example

Find 16 in the matrix:

Only 3 steps instead of checking all 12 cells!

Part 2: Median of Two Sorted Arrays

The Two Rivers Story

Imagine two rivers flowing with numbers:

• River A: [1, 3, 8, 9, 15]
• River B: [7, 11, 18, 19, 21, 25]

You need to find the middle number if all waters merged!

What is a Median?

The median is the “middle child” of a sorted list:

• Odd length: The one in the center
• Even length: Average of two center numbers

Merged: [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]

• 11 numbers → median is the 6th → 11

The Brute Force Way (SLOW)

// Don't do this! O(m+n) time
int[] merged = merge(nums1, nums2);
return merged[merged.length / 2];

The Genius Binary Search Way

Instead of merging, we PARTITION both arrays!

graph TD
    A["Arrays A and B"] --> B["Binary search on smaller array"]
    B --> C["Find partition point"]
    C --> D["Left half from both arrays"]
    C --> E["Right half from both arrays"]
    D --> F["Max of left side"]
    E --> G["Min of right side"]
    F --> H["Calculate median"]
    G --> H

The Partition Magic

We split BOTH arrays so that:

• Left side has exactly HALF of all numbers
• Every number on left is smaller than every number on right

Array A: [1, 3, | 8, 9, 15] Array B: [7, 11, 18, | 19, 21, 25]

Check: All left (1,3,7,11,18) ≤ All right (8,9,15,19,21,25)?

Wait, 18 > 8! Not valid. Adjust partition!

The Algorithm

public double findMedianSortedArrays(
        int[] nums1, int[] nums2) {
    // Always search on smaller array
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(
            nums2, nums1);
    }

    int m = nums1.length;
    int n = nums2.length;
    int left = 0, right = m;

    while (left <= right) {
        int partA = (left + right) / 2;
        int partB = (m + n + 1) / 2 - partA;

        int maxLeftA = (partA == 0)
            ? Integer.MIN_VALUE
            : nums1[partA - 1];
        int minRightA = (partA == m)
            ? Integer.MAX_VALUE
            : nums1[partA];
        int maxLeftB = (partB == 0)
            ? Integer.MIN_VALUE
            : nums2[partB - 1];
        int minRightB = (partB == n)
            ? Integer.MAX_VALUE
            : nums2[partB];

        if (maxLeftA <= minRightB &&
            maxLeftB <= minRightA) {
            // Perfect partition!
            if ((m + n) % 2 == 0) {
                return (Math.max(maxLeftA, maxLeftB)
                    + Math.min(minRightA, minRightB))
                    / 2.0;
            } else {
                return Math.max(maxLeftA, maxLeftB);
            }
        } else if (maxLeftA > minRightB) {
            right = partA - 1;
        } else {
            left = partA + 1;
        }
    }
    return 0.0;
}

Visual Walk-Through

A = [1, 2], B = [3, 4]

Total = 4 elements, need 2 on each side.

Median = (max(2,−∞) + min(∞,3)) / 2 = (2 + 3) / 2 = 2.5

Why O(log(min(m,n)))?

We only binary search on the smaller array! Even if one array has 1 million items and the other has 10, we only do ~4 steps!

Key Takeaways

2D Matrix Search

• Treat sorted 2D grid as 1D sorted array
• Use row = mid / cols, col = mid % cols
• Time: O(log(m×n))

Median of Two Sorted Arrays

• Binary search to find correct partition
• Always search on smaller array
• Time: O(log(min(m,n)))

The Treasure Hunter’s Wisdom

“A wise hunter doesn’t check every hiding spot. They use clever tricks to eliminate half the possibilities each time!”

Binary search isn’t just about finding things faster — it’s about thinking smarter. When you see a sorted structure, your brain should whisper: “Can I cut this in half?”

Now go find those treasures! 🏆