74. Search a 2D Matrix

Problem

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, 50]
]
target = 3
Output: true

Example 2:

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

Problem Summary

Write an efficient algorithm to determine whether a target value exists in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Solution Approach

• Given a two-dimensional matrix whose values increase as the matrix indices increase, design an algorithm that can efficiently find a number in this matrix. If found, output true; if not found, output false.
• Although it is a two-dimensional matrix, due to its special ordering property, it can be completely treated as a one-dimensional matrix by index; row and column coordinate conversion is just needed. Finally, use binary search to search directly.

Code

package leetcode

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