搜索二维矩阵

题目链接

搜索二维矩阵

题目描述

注意点

• 每行中的整数从左到右按非严格递增顺序排列
• 每行的第一个整数大于前一行的最后一个整数
• 1 <= matrix.length, matrix[0].length <= 100

解答思路

• 先二分查找找到target所处的行，找到行后再二分查找找到target所处的列即可

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        int top = 0, bottom = row - 1;
        while (top <= bottom) {
            int rowMid = (top + bottom) / 2;
            if (matrix[rowMid][0] > target) {
                bottom = rowMid - 1;
            } else if (matrix[rowMid][col - 1] < target) {
                top = rowMid + 1;
            } else {
                int left = 0, right = col - 1;
                while (left <= right) {
                    int colMid = (left + right) / 2;
                    if (matrix[rowMid][colMid] == target) {
                        return true;
                    }
                    if (matrix[rowMid][colMid] > target) {
                        right = colMid - 1;
                    } else {
                        left = colMid + 1;
                    }
                }
                return false;
            }
        }
        return false;
    }
}

关键点

• 二分查找的思想
• 如果target介于某一行的最小值和最大值之间，且在该行没有找到target，说明二维矩阵中肯定没有target