leetcode/algorithms/SearchA2dMatrix/solution.js at master · P-ppc/leetcode · GitHub

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
42
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let m = matrix.length,
        n = m == 0 ? 0 : matrix[0].length
    if (m == 0 || n == 0)
        return false

    let low = 0,
        high = m - 1,
        rowIndex = -1
    while (low <= high) {
        let mid = parseInt((low + high) / 2)
        if (matrix[mid][n - 1] < target)
            low = mid + 1
        else if (matrix[mid][0] > target)
            high = mid - 1
        else {
            rowIndex = mid
            break
        }
    }
    if (rowIndex == -1)
        return false

    low = 0
    high = n - 1
    while (low <= high) {
        let mid = parseInt((low + high) / 2)
        if (matrix[rowIndex][mid] < target)
            low = mid + 1
        else if (matrix[rowIndex][mid] > target)
            high = mid - 1
        else
            return true
    }

    return false
};