[LeetCode] 74. Search a 2D Matrix

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.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Thought process:

Given the properties of the matrix, it can be thought as a sorted list which is folded into a matrix. The idea is to treat it as a sorted list and use the regular binary search. Given an index in a list, its row in the matrix is index / width and its column is index % width.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; if (m == 0) { return false; } int n = matrix[0].length; if (n == 0) { return false; } int left = 0; int right = m * n - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; int num = matrix[mid / n][mid % n]; if (num == target) { return true; } if (num < target) { left = mid; } else { right = mid; } } if (matrix[left / n][left % n] == target || matrix[right / n][right % n] == target) { return true; } return false; } }

Time complexity:
Say the matrix's height is a and width is b. The time complexity is O(log(ab)).