原题链接:
https://leetcode.cn/problems/search-a-2d-matrix/description/

解法1: 二次二分

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
/**
    两次二分
 */
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 二分合适的行
        int l = -1 , r = matrix.length;
        while(l + 1 < r){
            int mid = l + r >> 1;
            // l target mid r
            if(matrix[mid][0] >= target){
                r = mid;
            }else{
                l = mid;
            }
        }

        int row = r;

        if( row >= matrix.length ||  row > 0 && matrix[row][0] > target ){
            row--;
        }

        // System.out.println(row);
        l = - 1 ;
        r = matrix[0].length;
        while(l + 1 < r){
            int mid = l + r >> 1;
            if(matrix[row][mid] >= target){
                r = mid;
            }else{
                l = mid;
            }
        }

        if(r >= matrix[0].length){
            return false;
        }

        return matrix[row][r] == target; 
    }
}

解法2: 一次二分

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

class Solution {
    public static int n;
    public static int m;
    
    public boolean searchMatrix(int[][] matrix, int target) {
        n = matrix.length;
        m = matrix[0].length;
        int l = -1 , r = n * m;

        while(l + 1 < r){
            int mid = l + r >> 1;
            int x = get(mid)[0], y = get(mid)[1];
            if(matrix[x][y] >= target){
                r = mid;
            }else{
                l = mid;
            }
        }

        if(r >= n * m){
            return false;
        }

        return matrix[get(r)[0]][get(r)[1]] == target; 
    }

    // 将一维 坐标转化为 二维
    public int [] get(int x){
        return new int []{x / m , x % m};
    }
}

解法3: 抽象BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public static int n,m;
    public boolean searchMatrix(int[][] matrix, int target) {
        // 右上角作为BST的根 其实也是二分的思想
        n = matrix.length;
        m = matrix[0].length;
        int x = 0 , y = m - 1;
         
        while(x < n && y >= 0){
            if(matrix[x][y] == target){
                return true;
            }

            if(matrix[x][y] > target){
                y--;
            }else{
                x++;
            }
        }

        return false;
    }
}