O(m*log(n)) solution in C++ - accepted.


  • 1
    I

    Very happy about that - looks like I can still remember to do some stuff right...

    That being said, shout if you can see anything blatantly stupid. Thanks!

    class Solution {
    public:
    
        bool searchRowBinary(vector<int>& a, int target, int start, int end) {
            if (start==end)
            {
                if (a[start]==target)
                    return true;
                else
                    return false;
            }
            else
            {
                int mid = (end+start)/2;    
                if(a[mid]>=target)
                    return searchRowBinary(a, target, start, mid);
                else 
                    return searchRowBinary(a, target, mid+1, end);
            }
        }
    
    
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            bool found = false;
            for(int i = 0; i < matrix.size(); i++)
            {
                if (matrix[i][0] <= target)
                {
                    found = searchRowBinary(matrix[i], target, 0, matrix[i].size()-1);
                }
                else
                    break;
      
                if (found)
                    break;
            }
            return found;
        }
    };

  • 1

    "shout if you can see anything blatantly stupid"

    The title.

    (Your solution isn't O(log(m*n)) but only O(m log n))


  • 0
    I

    True! Thanks for pointing out. I will try to amend the title.


  • 0
    F

    My code improves this algorithm.

    The concept is to narrow the range each time we search a row.

    For example, we have a matrix like:

    1 5 9 10...

    2 6 11 21 ...

    4 7 20 30...

    and the target is 6.

    When searched the first line, your algorithm is going to search:

    2 6 11 21 ...

    4 7 20 30...

    But in fact we only need to search, as 9 in the first row is larger than 6:

    2 6

    4 7

    Because the right part is impossible.

    In addition, I replace binary search with linear search when the range get small.


Log in to reply
 

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