leetcode/74-Search-a-2D-Matrix/index2.js at master · fa-ge/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
43
44
45
46
47
48
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */

function bSearchRange(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (target > arr[mid]) {
            low = mid + 1
        } else if (target < arr[mid]) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return low - 1
}

function bSearch(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (target > arr[mid]) {
            low = mid + 1
        } else if (target < arr[mid]) {
            high = mid - 1
        } else {
            return true
        }
    }
    return false
}

var searchMatrix = function(matrix, target) {
    const firstColArr = matrix.map(val => val[0])
    const row = bSearchRange(firstColArr, target)
    if (row === -1) {
        return false
    }
    return bSearch(matrix[row], target)
};

console.log(searchMatrix([[1]],0))