[LeetCode] 74. Search a 2D Matrix

Posted on | In

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:

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

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

Explanation

  1. Because the last element of the row is the biggest number of that row, if the target element is greater than that last number, the target element cannot be on the current row and the rows above the current row.

  2. We can use binary search method to find out the target row that the target element is in, then we use binary search method again to find out if the target element is in the target row.

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
34
35
36
37
38
39
40
41
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int rowStart = 0, rowEnd = matrix.length-1;
        int colStart = 0, colEnd = matrix[0].length-1;
        int targetRow = 0;

        while (rowStart < rowEnd) {
            int mid = rowStart + (rowEnd - rowStart) / 2;
            if (matrix[mid][colEnd] == target) {
                return true;
            } else if (matrix[mid][colEnd] < target) {
                rowStart = mid + 1;
            } else {
                rowEnd = mid;
            }
        }
        if (matrix[rowStart][colEnd] >= target) {
            targetRow = rowStart;
        } else {
            return false;
        }

        while (colStart < colEnd) {
            int mid = colStart + (colEnd - colStart) / 2;
            if (matrix[targetRow][mid] == target) {
                return true;
            } else if (matrix[targetRow][mid] < target) {
                colStart = mid + 1;
            } else {
                colEnd = mid;
            }
        }
        if (matrix[targetRow][colStart] == target) {
            return true;
        } else {
            return false;
        }
    }
}