Advanced Binary Search

🔍 Advanced Binary Search: Finding Needles in Giant Haystacks

The Story of the Super Detective

Imagine you’re a detective with a magical magnifying glass. This magnifying glass can look at the MIDDLE of any pile and instantly tell you: “What you’re looking for is in the LEFT half” or “What you’re looking for is in the RIGHT half.”

That’s Binary Search — cutting your search in half with every look!

Now, let’s become SUPER detectives who can:

1. Search in a 2D Matrix — Find treasure on a map with rows and columns
2. Find the Median of Two Sorted Arrays — Find the middle person when two lines merge

🗺️ Search in 2D Matrix

The Treasure Map Story

Picture a treasure map drawn as a grid. The map has a special rule:

• Numbers increase as you go RIGHT →
• Numbers increase as you go DOWN ↓
• Each row’s first number is bigger than the last row’s last number

It looks like a snake slithering through the grid!

[  1,  3,  5,  7 ]    ← Row 0
[ 10, 11, 16, 20 ]    ← Row 1
[ 23, 30, 34, 60 ]    ← Row 2

The snake goes: 1→3→5→7→10→11→16→20→23→30→34→60

The Magic Trick

Since the numbers are like one long sorted line (the snake), we can use our magical magnifying glass (binary search)!

Step 1: Pretend the 2D grid is a 1D line Step 2: Use binary search on that line Step 3: Convert back to row and column

How to Convert?

If you have a grid with m rows and n columns:

Example: Find 11 in the Matrix

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

m = 3 rows, n = 4 columns
Total = 12 items (0 to 11)

Detective Work:

1. Start: left = 0, right = 11
2. Middle: mid = 5
   • Row = 5 ÷ 4 = 1
   • Col = 5 % 4 = 1
   • Value at [1][1] = 11 ✅ FOUND!

graph TD
    A["Start: 0 to 11"] --> B["Mid = 5"]
    B --> C["Row = 5÷4 = 1"]
    B --> D["Col = 5%4 = 1"]
    C --> E["matrix[1][1] = 11"]
    D --> E
    E --> F["🎉 Found!"]

The Code (Simple Version)

function searchMatrix(matrix, target) {
  if (!matrix.length) return false;

  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = Math.floor((left+right)/2);
    const row = Math.floor(mid / n);
    const col = mid % n;
    const val = matrix[row][col];

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

Why So Fast?

⚖️ Median of Two Sorted Arrays

The Two Lines Story

Imagine two lines of kids waiting for ice cream, already sorted by height:

Line A: 🧒 (short) → 👦 → 👧 → 🧑 (tall) Line B: 👶 (short) → 🧒 → 👦 → 🧔 (tall)

The median is the kid standing in the exact middle when both lines merge!

What is a Median?

The median is the middle value:

• If 5 kids total → median is kid #3
• If 6 kids total → median is average of kids #3 and #4

Merged: [1, 2, 3, 4, 5, 6]
              ↑   ↑
           Middle kids
Median = (3 + 4) / 2 = 3.5

The Naive Way (Slow)

1. Merge both arrays
2. Sort them
3. Find the middle

Problem: This takes O(m+n) time. We want O(log(m+n))!

The Smart Way (Binary Search!)

Instead of merging, we partition both arrays!

The Big Idea:

• Split array A somewhere
• Split array B somewhere
• Make sure left halves ≤ right halves
• The median is at the partition!

Visual Partition

Array A: [1, 3, | 8, 9]
Array B: [2, 4, 5, | 7]
         ←LEFT→   ←RIGHT→

Left side:  1, 3, 2, 4, 5
Right side: 8, 9, 7

For valid partition:
- A's left-max (3) ≤ B's right-min (7) ✓
- B's left-max (5) ≤ A's right-min (8) ✓

The Partition Rules

graph TD
    A["Partition both arrays"] --> B{"Check conditions"}
    B -->|"maxLeftA ≤ minRightB<br>AND<br>maxLeftB ≤ minRightA"| C["✅ Valid!&lt;br&gt;Calculate median"]
    B -->|"maxLeftA > minRightB"| D["Move partition A left"]
    B -->|"maxLeftB > minRightA"| E["Move partition A right"]
    D --> A
    E --> A

Step-by-Step Example

Find median of [1,3] and [2]

A: [1, 3]  (length = 2)
B: [2]     (length = 1)
Total = 3 (odd, so one middle)

Partition Search:

1. Binary search on smaller array (B)
2. Try partition at B[0]:
   • A partition auto-adjusts
   • Check if valid

Attempt 1:
A: [1 | 3]    partitionA = 1
B: [ | 2]     partitionB = 0

Left:  A[0]=1
Right: A[1]=3, B[0]=2

maxLeft = 1
minRight = min(3,2) = 2

1 ≤ 2 ✓ Valid!

Total odd → Median = minRight = 2

The Code

function findMedian(nums1, nums2) {
  // Ensure nums1 is smaller
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }

  const m = nums1.length;
  const n = nums2.length;
  let lo = 0, hi = m;

  while (lo <= hi) {
    const pA = Math.floor((lo + hi) / 2);
    const pB = Math.floor((m+n+1)/2) - pA;

    const maxLeftA = pA === 0
      ? -Infinity : nums1[pA-1];
    const minRightA = pA === m
      ? Infinity : nums1[pA];
    const maxLeftB = pB === 0
      ? -Infinity : nums2[pB-1];
    const minRightB = pB === n
      ? Infinity : nums2[pB];

    if (maxLeftA <= minRightB &&
        maxLeftB <= minRightA) {
      // Found partition!
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeftA,maxLeftB)
              + Math.min(minRightA,minRightB))/2;
      }
      return Math.max(maxLeftA, maxLeftB);
    }

    if (maxLeftA > minRightB) {
      hi = pA - 1;
    } else {
      lo = pA + 1;
    }
  }
}

Why Binary Search Works Here

🎯 Key Takeaways

Search in 2D Matrix

1. Flatten the grid mentally (it’s really one sorted line)
2. Use index math to convert position → row/col
3. Time: O(log(m×n)) — super fast!

Median of Two Sorted Arrays

1. Binary search the partition, not the merge
2. Always search the smaller array
3. Check partition validity with cross-comparisons
4. Time: O(log(min(m,n))) — blazing fast!

graph TD
    subgraph "Advanced Binary Search"
    A["2D Matrix Search"] --> B["Treat as 1D array"]
    B --> C["Binary search on index"]
    C --> D["Convert index to row/col"]

    E["Median of Two Arrays"] --> F["Binary search partition"]
    F --> G["Validate cross-elements"]
    G --> H["Calculate median at partition"]
    end

🚀 You’re Now a Super Detective!

You’ve learned TWO powerful techniques:

1. 2D Matrix Search — Flatten and conquer!
2. Median of Two Arrays — Partition and compare!

Both use the same magic: cutting the problem in half with every step.

Next time you see a sorted structure, remember:

“Can I use binary search here?”

The answer is usually YES! 🎉