74. Search a 2D Matrix

LeetCode 74. Search a 2D Matrix****

Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.

• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 100

• -104 <= matrix[i][j], target <= 104

Tags

Binary Search, Array

Solution

This is a 2D version of Binary Search problem. Based on the Binary Search template, we only need to convert any 1D index to 2D, with the formula below, so that we can position that element in the given matrix.

$Flattened1DArray[i] = 2DMatrix[i/cols][i\pmod{cols}]$

Complexity

• Time complexity: $O(log(n))$

• Space complexity: $O(1)$

Code

func searchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	start, end := 0, rows*cols-1
	for start+1 < end {
		mid := start + (end-start)/2
		if center := matrix[mid/cols][mid%cols]; center > target {
			end = mid
		} else if center < target {
			start = mid
		} else {
			return true
		}
	}
	if matrix[start/cols][start%cols] == target || matrix[end/cols][end%cols] == target {
		return true
	}
	return false
}