📃 题目描述

题目链接：剑指 Offer 04. 二维数组中的查找 (opens new window)

🔔 解题思路

二分查找

每行每行的二分查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length;
        int col = matrix[0].length;

        int right = col - 1;
        for (int i = 0; i < row; i ++) {
            int left = 0;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (matrix[i][mid] == target) {
                    return true;
                }
                else if (matrix[i][mid] < target) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
        }

        return false;
    }
}

时间复杂度 O(NLogN)

线性查找（推荐）

解题思路：利用二维数组行列递增特性

主要思路：

由于行列递增，可以得出：

• 在一列中的某个数字，其上的数字都比它小
• 在一行中的某个数字，其右的数字都比它大

搜索流程：

• 首先从数组左下角搜索.
• 如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
• 查找到 target,返回true; 如果越界，返回false;

示例如下：

时间复杂度 O(M + N)

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length;
        int col = matrix[0].length;

        int i = row - 1;
        int j = 0;

        while (i >= 0 && j < col) {
            if (matrix[i][j] == target) {
                return true;
            }
            // 右移 增大
            else if (matrix[i][j] < target) {
                j ++;
            }
            // 上移 减小
            else {
                i --;
            }
        }

        return false;
    }
}