Multi-dimension Binary Search

You are given an m x n 2-D integer array matrix and an integer target.

• Each row in matrix is sorted in non-decreasing order.
• The first integer of every row is greater than the last integer of the previous row.

Return true if target exists within matrix or false otherwise.
Can you write a solution that runs in O(log(m * n)) time?

Example 1:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true

Example 2:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10000 <= matrix[i][j], target <= 10000

1. Sequential Level Bin Search O(log(m * n))

High-level idea, binary search to find outer array - guessing array target element belong to:

1. Search over rows -> found a row
2. Search inside that row

package main 
import "fmt"

func searchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	top,bot :=0,rows-1
	for top <= bot {
		mid := (top+bot)/2
		if matrix[mid][cols-1] < target {
			top = mid + 1
		} else if matrix[mid][0] > target {
			bot = mid - 1
		} else {
			break
		}
	}
	
	if !(top <= bot) {
		return false
	}
	
	row:=(top+bot)/2
	l,r:=0,len(matrix[row])-1
	
	for l <= r {
		mid := (l+r)/2
		if matrix[row][mid] < target {
			l = mid+1
		} else if matrix[row][mid] > target {
			r = mid-1
		} else {
			return true
		}
	}
	
	return false
}

func main() { 
	matrix := [][]int{ 
		{1, 3, 5, 7},
		{10, 11, 16, 20},
		{23, 30, 34, 60},
	}
	fmt.Println(searchMatrix(matrix, 10)) 
}

2. Flattened Bin Search O(log(n))

Because the matrix is sorted row-wise and each row is sorted left-to-right, the entire matrix behaves like one big sorted array.

If we imagine flattening the matrix into a single list, the order of elements doesn't change.

This means we can run one binary search from index 0 to ROWS * COLS - 1.
For any mid index m, we can map it back to the matrix using:

• row = m // COLS
• col = m % COLS
  This lets us access the correct matrix element without actually flattening the matrix.

package main 
import "fmt"

func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1
	
	for left <= right {
		mid := (left + right) / 2
		val := matrix[mid/n][mid%n]
		if val < target {
			left = mid + 1
		} else if val > target {
			right = mid - 1
		} else {
			return true
		}
	}
	
	return false
}

func main() { 
	matrix := [][]int{ 
		{1, 3, 5, 7},
		{10, 11, 16, 20},
		{23, 30, 34, 60},
	}
	fmt.Println(searchMatrix(matrix, 10)) 
}

Related:
binary-search