leetcode/typescript/74-Search-a-2D-Matrix.ts at main · MukulAppDev/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
function searchMatrix(matrix: number[][], target: number): boolean {
    const rows = matrix.length;
    const columns = matrix[0].length;

    let top = 0;
    let bot = rows - 1;

    while (top <= bot) {
        let row = Math.floor((top + bot) / 2);
        if (target > matrix[row][columns - 1]) {
            top = row + 1;
        } else if (target < matrix[row][0]) {
            bot = row - 1;
        } else {
            break;
        }
    }

    if (top > bot) {
        return false;
    }

    let row = Math.floor((top + bot) / 2);
    let l = 0;
    let r = columns - 1;

    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (target > matrix[row][m]) {
            l = m + 1;
        } else if (target < matrix[row][m]) {
            r = m - 1;
        } else {
            return true;
        }
    }

    return false;
}