/ Data Structure and Algorithms  

Leetcode 74. Search a 2D Matrix

Question



Search a value in an m x n matrix, determine if it exists.

Similar Questions

Solution

As the martix is ordered, there is no doubt that we need to use binary search. First find which row the target belongs to, then use binary search to determine. We just need to consider how to convert the index into the row and column of the matrix. To do so, we can use division and mod.

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
// matrix is empty
if (matrix.length == 0 || matrix[0].length == 0) {
    return false;
}

int col = matrix[0].length;

// loop each row, find which row the target belongs to
for (int[] ints : matrix) {
    // target in this row
    if (target >= ints[0] && target <= ints[col - 1]) {
        // use binary search to this row
        int low = 0;
        int high = col - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (target == ints[mid]) {
                return true;
            } else if (target < ints[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return false;
    }
}

return false;