题目描述

解题思路

二分查找

代码

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        //判断是否为空数组
        if(m==0) return false;
        int n = matrix[0].length;
        int idx,idxElement;
        int left=0,right=m*n-1;
        //注意这里要写的是<=
        while(left<=right){
            //计算中间值
            idx = (left+right)/2;
            //在原数组中对应的位置
            idxElement=matrix[idx/n][idx%n];
            //二分查找
            if(idxElement==target){
                return true;
            }else if(idxElement<target){
                left=idx+1;
            }else{
                right=idx-1;
            }
        }
        return false;
    }

复杂度分析

• 时间复杂度 : 由于是标准的二分查找，时间复杂度为O(\log(m n))。
• 空间复杂度 : O(1)。