[leetcode] day103 search two-dimensional matrix II

subject

240. Search for a two-dimensional matrix II【 secondary 】

Answer key

Two points search

My father, my fellow villagers , Next, we come to binary search in two-dimensional space ！

It's actually a big name , The essence is binary search of one-dimensional array . Binary search for each row of the two-dimensional array , Finally get the target value .

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
    
        int m=matrix.length,n=matrix[0].length;
        // Line by line binary search 
        for(int[] row:matrix){
    
            if(search(row,target))
                return true;
        }
        return false;
    }
    // Two points search 
    public boolean search(int[] num,int target){
    
        int low=0,high=num.length-1;
        while(low<=high){
    
            int mid=(low+high)/2;
            if(num[mid]==target)
                return true;
            else if(num[mid]<target)
                low=mid+1;
            else
                high=mid-1;
        }
        return false;
    }
}

Time complexity ：$O(mlogn)$

Spatial complexity ：$O(1)$

Z Font search

From matrix's Upper right corner Start ,
if matrix[x][y]> The target , The left one , namely y–;
if matrix[x][y]< The target , Move one down , namely x++;

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
    
        int m=matrix.length,n=matrix[0].length;
        int x=0,y=n-1;
        while(x<m && y>=0){
    
            int num=matrix[x][y];
            if(num==target)
                return true;
            else if(num<target)
                x++;// Move down 
            else
                y--;// Move left 
        }
        return false;
    }
}

Time complexity ：$O(m+n)$

Spatial complexity ：$O(1)$