Sword finger offer04 Search in two-dimensional array [medium]

The finger of the sword Offer 04. Search in a two-dimensional array 【 secondary 】

Title Description

In a n * m In a two-dimensional array , Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete an efficient function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

Example :

The existing matrix matrix as follows ：

Given target = 5, return true.
Given target = 20, return false.

Limit ：

0 <= n <= 1000
0 <= m <= 1000

Java Code

Violence solution

Simple and rough, two-level traversal, one by one .

class Solution {
    
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
        for(int i = 0;i<matrix.length;i++){
    
            for(int j = 0;j<matrix[i].length;j++){
    
                if(matrix[i][j]==target){
    
                    return true;
                }
            }
        }
        return false;
    }
}

Official solution

Start from the upper right corner of the two-dimensional array . If the current element is equal to the target value , Then return to true. If the current element is larger than the target value , Move to the left column . If the current element is less than the target value , Move to the next line .

Be careful ： It can be proved that this method will not miss the target value . If the current element is larger than the target value , It indicates that all elements below the current element must be greater than the target value , Therefore, it is impossible to find the target value by looking down , Looking to the left may find the target value . If the current element is less than the target value , It indicates that all elements on the left of the current element must be less than the target value , Therefore, it is impossible to find the target value by looking to the left , Look down and you may find the target value .

class Solution {
    
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
            return false;
        }
        int row=0,column=matrix[0].length-1;
        while(row<matrix.length&&column>=0){
    
           if(matrix[row][column]==target){
    
               return true;
           }else if(matrix[row][column]<target){
    
               row++;
           }else{
    
               column--;
           }
        }
        
        return false;
    }
}

Add ideas ：

The key is to be able to think , Traverse from the upper right corner of the two-dimensional array .

• Because the upper left and lower right corners are the maximum and minimum values of the array respectively , All have two directions to choose at the same time , Unable to determine the unique .
• And the lower left and upper right can , Take the upper right corner for example , It is the maximum value of the line , Column minimum . If it is smaller than the target , You can exclude this line of data , Column +1（ Because it is already the maximum value of this line , Smaller than the target value , It means that this line of data is too small , There can be no target value . So listed +1 Abandon .）

Another idea is ：

• Look in the upper right corner . This matrix is actually like a Binary Search Tree Binary search tree .