1.题目描述

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

1
2
3
4
5
6
7
8
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

1
2
3
4
5
6
7
8
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //获取行 列值
        int row = matrix.length;
        //判断是否有元素
        if (row == 0){
            return false;
        }
        int col = matrix[0].length;
        if (col == 0){
            return false;
        }

        //判断在哪一行
        int index = 0;
        for (int i = 0; i < row; i++) {
            if (matrix[i][col-1] >= target){
                //找到了行
                index = i;
                //System.out.println(index);

                //退出循环
                break;
            }
        }

        //正常的二分
        int leftIndex = 0;
        int rightIndex = col-1;
        //寻找
        while (leftIndex != rightIndex){
            int middle = (leftIndex + rightIndex) / 2;

            if (matrix[index][middle] >= target){
                rightIndex = middle;
            }else {
                leftIndex = middle+1;
            }
        }
        //判断是不是
        if (matrix[index][leftIndex] == target){
            return true;
        }

        return false;
    }
}