[recommend for beginners]clean C++ implementation with detailed explanation


  • 0

    As you can see, THIS problem test your grasp of the binary-search-method.

    The key is to set the open and close condition. In this problem, we all set the

      end=n     end=m
    

    means that the end violates the condition and the start satisfy the condition.

    so, we will return start finally.

      class Solution {
        public:
            bool searchMatrix(vector<vector<int>>& matrix, int target) {
                int m=matrix.size();
                if(!m)  return false;
                int n=matrix[0].size();
                /*** binary-search the line-index ***/
                int start=0, end=m, mid;
                /*** [start, end) ***/
                while(end-start > 1){
                    mid=(start+end)/2;
                    if(matrix[mid][0]<=target)  start=mid;
                    else if(matrix[mid][0]>target)  end=mid;
                }
                int row=start;
                cout<<"row:"<<row<<endl;
                /*** binary-search the line-index ***/
                start=0;
                end=n;
                /*** [start, end) ***/
                while(end-start > 1){
                    mid=(start+end)/2;
                    if(matrix[row][mid]<=target)  start=mid;
                    else if(matrix[row][mid]>target)  end=mid;
                }
                return matrix[row][start]==target;
            }
        };

  • 0
    X

    It takes 16ms in my case, while if I naively use one pass to search for the line index, the running time is 12ms. I agree that this is O(log(m)+log(n)) and the latter is O(m+log(n)). Any idea why?


  • 0

    Interesting ! Can you post your code here ?


  • 0
    X
    class Solution {
        bool BinarySearch(vector<int> v, int target)
        {
            int l = 0, r = v.size();
            while(l< v.size() && l<r)
            {
                int mid = l + (r-l)/2;
                if (v[mid] == target)
                    return true;
                else if (v[mid] < target)  //search right of mid
                    l = mid+1;
                else r = mid;
            }
            return false;
        }
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.empty()) return false;
            
            int m = matrix.size();
            int n = matrix[0].size();
            
            int i = 0;
            while ( i<m && matrix[i][n-1] < target)  //O(m) search through rows
                i++;
            if (i == m) return false;
    
            return BinarySearch(matrix[i], target);  //O(log n) search through column
            
        }
    };

  • 0
    X

    Nvm, I think it should just be due to the the reason that the test cases are not strong enough, which is pointed by the other thread. An O(mn) approach in C++ can get 12ms, too. =.=

        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.empty()) return false;
            for (auto line: matrix)
                for(auto item: line)
                    if (target == item)
                        return true;
            return false;
    }

  • 0

    Interesting! Oops, how can that happens ? We have to admit the Leetcode test cases have many problems about how to reveal the complexity of our different implementations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.