search in a 2D matrix 2

双重二分法

code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int s = 0;
        int e = m-1;
        int upbound = 0;

        while(s+1 < e)
        {
            int mid = (s+e)/2;
            if(matrix[mid][0] > target)
            {
                e = mid;
            }
            else
            {
                s = mid;
            }
        }

        if(matrix[s][0] <= target)
        {
            upbound = s;  
        }

        if(matrix[e][0] <= target)
        {
            upbound = e;  
        }

        for(int i = 0; i<=upbound; i++)
        {
            int s = 0;
            int e = n-1;

            while(s+1 < e)
            {
                int mid = (s+e)/2;
                if(matrix[i][mid] == target)
                {
                    return true;
                }
                else if(matrix[i][mid] > target)
                {
                    e = mid;
                }
                else 
                {
                    s = mid;
                }
            }

            if(matrix[i][s] == target)
            {
                return true;
            }

            if(matrix[i][e] == target)
            {
                return true;
            }
        }

        return false;
    }
};