剑指Offer 04. 二维数组中的查找

原题链接

思路

• 题目中说，每一行都是 从左向右递增的，在一个递增的序列中，查找某个数是否是存在的，二分即可
• 注意对边界进行判断
• 时间复杂度：O(nlogn)

代码

class Solution {
    public boolean check(int[] nums,int target) {
        int l = 0;
        int r = nums.length - 1;
        while(l < r) {
            int mid  = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] == target;
    }
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n = matrix.length;
        if(n == 0) return false;
        for(int i = 0; i < n; i++) {
            if(matrix[i].length == 0) continue;
            if(check(matrix[i],target)) return true;
        }
        return false;
    }
}