Search two-dimensional matrix [clever use of bisection + record solution different from inserting bisection]

Preface

An ordered array or something , It should be closely related to the dichotomy . But dichotomy has many details , It is mainly divided into two parts / Two point insertion search position . Today, I have reached this question , Requirements are different from binary insertion to find the position , It's looking for something better than target Just a small position , Not the last one .

One 、 Search for a two-dimensional matrix

Two 、 Record solutions that are different from inserting dichotomy

package everyday.medium;

//  Search for a two-dimensional matrix 
public class SearchMatrix {
    
    /* target： Quickly search whether there is a target value in the matrix .  Every row of the matrix has a characteristic , That's order , And the columns are ordered , But this order is not true . Think of a matrix as a bit matrix ( tile ), The answer is known .  So the line and column can be divided twice . */
    public boolean searchMatrix(int[][] matrix, int target) {
    
        // bug1: Column before row , It should be listed first .
        //  Dichotomy target  In the line .
        int low = 0, high = matrix.length - 1;
        while (low < high) {
    
            //  This is a place worth recording 
            //  Different from inserting dichotomy , What we are looking for here is just like this large number of positions , Instead of the latter position .
            //  It's also very simple ,int mid = low + (high - low + 1 >>> 1);  coordination  else low = mid;
            int mid = low + (high - low + 1 >>> 1);
            int midVal = matrix[mid][0];
            if (midVal > target) high = mid - 1;
            else low = mid;
        }
        //  look for target  In which column .
        int col = binarySearch(matrix[low], target);

        return matrix[low][col] == target;
    }

    private int binarySearch(int[] nums, int target) {
    
        int low = 0, high = nums.length - 1;
        while (low < high) {
    
            //  Take it up , It is different from the usual ascending insertion , Here we need to find a small place just like ourselves .
            int mid = low + (high - low + 1 >>> 1);
            int midVal = nums[mid];
            if (midVal > target) high = mid - 1;
            else low = mid;
        }
        return low;
    }
}

summary

1） Order and dichotomy are closely linked , Be connected in your mind .
2） Different from the solution of inserting dichotomy .

reference

[1] LeetCode Search for a two-dimensional matrix