[LeetCode] Problem 74 - Search a 2D Matrix

Posted on | In ,

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

No.1

Input:

1
2
3
4
5
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

target = 3

Output: true

No.2

Input:

1
2
3
4
5
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

target = 13

Output: false

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length < 1)
        return false;
    
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0;
    int right = m * n - 1;

    while (left <= right) {
        int mid = (left + right) >> 1;
        int num = matrix[mid / n][mid % n];

        if (num < target)
            left = mid + 1;
        else if (num > target)
            right = mid - 1;
        else
            return true;
    }

    return false;
}