DEV Community

Dev Cookies
Dev Cookies

Posted on

Binary Search Patterns Series — Blog 4: 2D Matrix & Advanced Variants

1. Binary Search in Row-wise & Column-wise Sorted Matrix

Problem:
Matrix is sorted row-wise and column-wise. Search for a target in O(m+n) or O(log(m*n)).

Example:

matrix = [ [1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16] ] target = 5 → Output: true
Enter fullscreen mode Exit fullscreen mode

1.1 Flatten 2D Matrix to 1D

Treat the matrix as a 1D sorted array:

public boolean searchMatrix(int[][] matrix, int target) { int n = matrix.length; int m = matrix[0].length; int low = 0, high = n*m - 1; while (low <= high) { int mid = low + (high - low)/2; int val = matrix[mid/m][mid%m]; if (val == target) return true; else if (val < target) low = mid + 1; else high = mid - 1; } return false; }
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(log(m*n))
Space Complexity: O(1)

1.2 Staircase Search (O(m+n))

Start from top-right corner:

public boolean searchMatrixStaircase(int[][] matrix, int target) { int row = 0, col = matrix[0].length - 1; while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) return true; else if (matrix[row][col] > target) col--; else row++; } return false; }
Enter fullscreen mode Exit fullscreen mode

2. Search in Infinite / Unknown Size Array

Problem: Array size unknown. Find target in O(log n).

Approach:

  1. Exponentially expand search range: low = 0, high = 1, 2, 4, 8... until arr[high] >= target.
  2. Apply normal binary search in [low, high]. 
public int searchInfiniteArray(ArrayReader reader, int target) { int low = 0, high = 1; while (reader.get(high) < target) { low = high; high = high * 2; } return binarySearch(reader, low, high, target); }
Enter fullscreen mode Exit fullscreen mode

Note: ArrayReader.get(index) returns large value if out of bounds.

3. Ternary Search for Unimodal Functions

Problem: Function f(x) first increases then decreases. Find maximum value.

Template:

double left = 0, right = 1000; while (right - left > 1e-6) { double mid1 = left + (right - left)/3; double mid2 = right - (right - left)/3; if (f(mid1) < f(mid2)) left = mid1; else right = mid2; } return f(left); // maximum value
Enter fullscreen mode Exit fullscreen mode

Use Case: Optimization problems, like finding peak in mountain array or maximizing profit.

4. Edge Cases & Tips

  1. For matrix search, always check matrix.length and matrix[0].length.
  2. Infinite array search: ensure exponential expansion does not overflow integer.
  3. Ternary search: stop condition depends on required precision.
  4. 2D to 1D mapping: row = mid / cols, col = mid % cols.

5. Problems to Practice

  • LeetCode 74: Search a 2D Matrix
  • LeetCode 240: Search a 2D Matrix II
  • LeetCode 275: H-Index II
  • LeetCode 852: Peak Index in a Mountain Array
  • Infinite array search variants (GeeksforGeeks)

✅ Blog 4 Summary:

  • Binary search in 2D matrices (flattened or staircase search)
  • Infinite / unknown-size array search
  • Ternary search for unimodal functions
  • Java implementation with edge cases

Next in Series — Blog 5

Binary Search Patterns Cheat Sheet & Edge Cases

  • Consolidation of all patterns
  • Overflow-safe mid calculations
  • Low/high boundary handling
  • First/last occurrence edge cases
  • Complete reference Java snippets

Top comments (0)