LeetCode 74. Search 2D matrix

Today I saw the dichotomy summary formula of snow vegetables , I'm confused 3 I understand it a little , Simple dichotomy can be slightly understood , Search the binary matrix , I still have a little trouble , Take advantage of some ideas , Make notes for your own review .

The original title is ：

Power button -74. Search the binary matrix

First of all, let's mention the dichotomy summary template of the snow cabbage boss ：

Snow vegetable - Two sub topics                 You can take a step-by-step look at the two-part explanation here

Binary search algorithm template - Snow vegetable     You can move here to see the binary template

This topic , Because all numbers are increasing in order , So you can use dichotomy

Because it's a two-dimensional array , It needs to be found in the middle middle, So first write the number of rows and columns

The two-dimensional array is shown in the figure ： 

Then its column number is a two-dimensional array matrix The length of ： matrix.length, The number of rows is the length of the first column ：matrix[0].length

Then set the leftmost left from 0 Start , Far right right It is That's ok × Column -1, Median middle It is left + （right - left） /2

then Set a check（t） function , there t Set the conditions yourself , Because all the numbers in this question are Orderly increase , I set For this condition A random number >=target, Because it's a binary array , So this number is ：matrix[mid /m][mid % m] , So I if The judgment condition is  matrix[mid /m][mid % m] >= target

Draw the picture according to this

here , According to your own conditions , take [L , R] It is divided into two paragraphs , On the far right is >=target Of , Then assume the midpoint middle On the right side , that It can be seen that , The left boundary of the right range is at the midpoint middle, Ask for this boundary , Its next screening range is [L , R] Turned into [ L , middle ] , If middle Fall on On the left side That is, as shown in the figure

Because the boundary you are looking for is middle The right side of the , And it doesn't belong to >target The scope of the , Then the screening range is determined by  [L , R] Turned into [ middle +1 , R ] , This will confirm if-else Of The executive part of

Again , If you choose the condition opposite to the above <=target , Then the scope at this time is the part on the left , You need to find the right boundary of the left part , If at this time middle Fell on the right side , Then the screening range is determined by  [L , R] Turned into [ L , middle -1 ], If it falls on the left , Then the screening range is determined by  [L , R] Turned into [ middle , R ] 

Finally, analyze and judge , When the array is empty , I can't find it at this time target, Then you have to return false：if(matrix.length==0 || matrix[0].length==0) return false;

If the array is not empty , But I can't find target, Return, too false：

if(matrix[r /m][r % m] != target) return false;

 

A certain number of two-dimensional arrays Abscissa 、 Vertical coordinate solution ：

cross ： Ordinal number  / Row number , In this way, we can get the number of lines

longitudinal ： Ordinal number % Row number , In this way, we can get the number of columns

for instance ：

In the picture 16 Of coordinate , Then press from 0 Start in order ,16 The order number of should be 6, Then use 6 Go to the above to get ：6 / 4 Rounding down =1,6 % 4=2

So at this time 16 The coordinate position of is ：[ 1 , 2 ]      first line , Second column （ That's ok 、 Columns are from 0 Start ）

In this way, you can write code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0 || matrix[0].length==0) return false;
        int n =matrix.length,m=matrix[0].length; //n Is the number of columns ,m Is the number of rows 
        int l =0, r=m *n -1;
        while(l <r){
            int mid = l + r >>1;
            if(matrix[mid /m][mid % m] >= target) r = mid;
            else l = mid+1;
        }
        if(matrix[r /m][r % m] != target) return false; 
        else return true;
    }
}