Lesson 1: finding the minimum of a matrix

subject ：AcWing 1452. Find the minimum of the matrix
Given a n×n Matrix , The matrix contains n×n individual Different from each other The integer of .

Define the minimum ： If the value of a number is smaller than that of all adjacent numbers , Then this value is called the minimum .

The adjacent numbers of a number refer to the four adjacent numbers in the upper, lower, left and right directions , Also note , The number at the boundary or corner may have less than four adjacent numbers .

Ask for in O(nlogn) Find the position of any minimum within the time complexity , And output its rows and columns .

The matrix in this question is hidden , You can use our preset int function query To get the value of a certain position in the matrix .

for example ,query(a,b) You can get the... In the matrix a Xing di b The value of the position of the column .

Be careful ：

The rows and columns of the matrix are from 0 Numbered starting .
query() Function cannot be called more than (n+2)×⌈log₂n⌉+n.
The answer is not unique , Output the position of any minimum value .
Data range
1≤n≤300, The integers in the matrix are int Within the scope of .

sample input ：

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

sample output ：

[0, 0]

Topic analysis ：
The first way to think about it is to start from the starting point and find something smaller than yourself , Keep looking for , Then we will definitely find the minimum （ Because the points are different ）
But the worst case is to visit n² Time .

The second method is dichotomy , First find the minimum value in the middle column , Then look at the left and right
1. If v<l,v<r that v Is the minimum
2. If l<v, Then there is a minimum on the left
3. If r<v, Then there is a minimum on the right
Why? ？
Suppose the right r<v, So in the middle mid This column is better than r Be big , Then we use the first method to find that it is definitely impossible to cross mid This column （ Because I will look for something better than r Small number ）, So in mid There must be a minimum on the right , This reduces the amount of search by half , Such repetition will finally find .

// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].

class Solution {
    
public:
    vector<int> getMinimumValue(int n) {
    
        typedef long long LL;
        const LL INF = 1e15;
        int l=0,r=n-1;
        while(l<r) //  Dichotomy 
        {
    
            int mid = l + r >> 1;
            LL val=INF;
            int k=0; //  Which row to save is the smallest 
            for(int i=0;i<n;i++)
            {
    
                int t=query(i,mid);
                if(t<val)
                {
    
                    val=t;
                    k=i;
                }
            }
            
            LL left=mid?query(k,mid-1):INF; //  Query left 
            LL right=mid+1<n?query(k,mid+1):INF; //  Query the right 
             
            if(val<left&&val<right)return {
    k,mid}; //  If the current point is the minimum 
            else if(left<val)r=mid-1;
            else l=mid+1;
        }
        
        int k;
        LL val=INF;
        for(int i=0;i<n;i++)
        {
    
            int t=query(i,l);
            if(t<val)
            {
    
                val=t;
                k=i;
            }
        }
        return {
    k,l};
    }
};