Advanced Binary Search

🔍 Advanced Binary Search: Finding Needles in Special Haystacks

The Treasure Hunt Analogy 🗺️

Imagine you’re a treasure hunter with a magic compass. This compass doesn’t just point north—it tells you if the treasure is “to the left” or “to the right” of where you’re standing. Instead of checking every spot, you keep cutting the search area in half until you find your treasure!

That’s Binary Search—the fastest way to find something in a sorted collection.

But what happens when your treasure map isn’t a simple line? What if it’s a grid or you need to find something hidden between two maps? That’s what Advanced Binary Search is all about!

🏠 Part 1: Search in 2D Matrix

The Story: The Library of Alexandria 📚

Picture a magical library where books are arranged in rows of shelves. Each shelf (row) has books sorted from left to right by page count. But here’s the magic: the first book on any shelf always has more pages than the last book on the shelf above it.

So if you flatten all the shelves into one long line, every book would be in perfect order!

What Is a 2D Matrix?

A 2D Matrix is like a grid or a table. Think of a chocolate box with rows and columns!

Matrix Example:
┌────┬────┬────┬────┐
│  1 │  3 │  5 │  7 │  ← Row 0
├────┼────┼────┼────┤
│ 10 │ 11 │ 16 │ 20 │  ← Row 1
├────┼────┼────┼────┤
│ 23 │ 30 │ 34 │ 60 │  ← Row 2
└────┴────┴────┴────┘

Special Property: Read left-to-right, top-to-bottom = fully sorted! 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60

The Clever Trick: Treat 2D as 1D! 🎩

Since the matrix is fully sorted when read in order, we can pretend it’s just one long list!

The Magic Formula:

• Total elements = rows × columns
• For any position mid in our imaginary 1D list:
  • row = mid ÷ columns (integer division)
  • col = mid % columns (remainder)

Visual Example: Finding Target = 16

Step 1: Imagine the grid as a line
Position: 0  1  2  3  4  5  6  7  8  9  10 11
Value:    1  3  5  7 10 11 16 20 23 30 34 60
          L              M                 R

Step 2: mid = (0+11)/2 = 5 → Value = 11
11 < 16, so go RIGHT

Step 3: L=6, R=11, mid=8 → Value = 23
23 > 16, so go LEFT

Step 4: L=6, R=7, mid=6 → Value = 16 ✅
FOUND IT!

Python Code

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    rows = len(matrix)
    cols = len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = (left + right) // 2
        # Convert 1D position to 2D
        row = mid // cols
        col = mid % cols
        value = matrix[row][col]

        if value == target:
            return True
        elif value < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

Why This Works 🧠

For a 1000×1000 matrix:

• Brute force: 1,000,000 checks 😫
• Binary Search: ~20 checks 🚀

🏆 Part 2: Median of Two Sorted Arrays

The Story: The Fair Judge 👨‍⚖️

Two kingdoms held separate archery competitions. Each kingdom ranked their archers from worst to best. Now the Grand Tournament wants to find the true middle archer—the one who would be exactly in the middle if all archers stood in one sorted line.

But here’s the challenge: there are too many archers to actually merge the lines! We need a clever way to find the middle without combining everything.

What Is a Median?

The median is the middle value when all numbers are sorted.

Odd count:  [1, 3, 5, 7, 9]  → Median = 5 (middle)
Even count: [1, 3, 5, 7]     → Median = (3+5)/2 = 4.0

The Challenge

Given two sorted arrays, find the median of the combined sorted array—but in O(log(min(m,n))) time!

nums1 = [1, 3]
nums2 = [2]
Combined = [1, 2, 3] → Median = 2

The Brilliant Insight 💡

Instead of merging arrays, we partition them!

Imagine cutting both arrays with a knife. The knife position in each array creates a “left side” and “right side.”

The Goal: Find cuts where:

1. Left side has exactly half the total elements
2. All elements on left ≤ all elements on right

Visual Partition

nums1 = [1, 3, 8, 9, 15]
nums2 = [7, 11, 18, 19, 21, 25]

Total = 11 elements → Left side needs 6 elements

One valid partition:
nums1: [1, 3] | [8, 9, 15]     (2 elements left)
nums2: [7, 11, 18, 19] | [21, 25] (4 elements left)
              ↑
         6 elements total on left!

Check: max(3, 19) ≤ min(8, 21)
       19 ≤ 8? NO! ❌

Try different cuts until condition is met!

The Algorithm

Binary search on the SMALLER array!

For each partition i in nums1:
  - j = (total_left) - i  (partition in nums2)
  - Check if partition is valid:
    - left1 ≤ right2 AND left2 ≤ right1
  - If valid, calculate median
  - If not, adjust binary search

Python Code

def findMedianSortedArrays(nums1, nums2):
    # Always search on smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    left, right = 0, m
    half = (m + n + 1) // 2

    while left <= right:
        i = (left + right) // 2
        j = half - i

        # Handle edge cases with infinity
        left1 = nums1[i-1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j-1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            # Valid partition found!
            if (m + n) % 2 == 1:
                return max(left1, left2)
            else:
                return (max(left1, left2) +
                        min(right1, right2)) / 2
        elif left1 > right2:
            right = i - 1
        else:
            left = i + 1

    return 0.0

Step-by-Step Example

nums1 = [1, 3]
nums2 = [2]

m=2, n=1, half=2

Iteration 1:
  i=1, j=1
  left1=1, right1=3
  left2=2, right2=∞

  Is 1 ≤ ∞? Yes ✓
  Is 2 ≤ 3? Yes ✓

  Valid! Total=3 (odd)
  Median = max(1, 2) = 2 ✅

The Mermaid Flow

graph TD
    A["Start"] --> B{m > n?}
    B -->|Yes| C["Swap arrays"]
    B -->|No| D["Keep order"]
    C --> D
    D --> E["Binary search on smaller"]
    E --> F["Calculate partition j"]
    F --> G{Valid partition?}
    G -->|Yes| H["Calculate median"]
    G -->|No| I["Adjust search bounds"]
    I --> E
    H --> J["Return result"]

🎯 Key Takeaways

Search in 2D Matrix

Median of Two Sorted Arrays

🌟 Why This Matters

These aren’t just interview problems—they’re thinking tools!

• 2D Matrix Search teaches you to see hidden structure
• Median finding teaches you to solve without doing the obvious thing

When you master these, you’re not just learning algorithms. You’re training your brain to find clever shortcuts in any problem!

🚀 Practice Challenges

1. What if the 2D matrix rows are sorted but the first element of a row isn’t greater than the last element of the previous row?
2. Can you find the median of three sorted arrays?
3. What if you need the k-th element instead of the median?

Remember: Every complex search problem is just binary search in disguise. Find the sorted property, and the solution reveals itself! 🔍✨