20 ms c++ solution using binary search on the whole matrix


  • 0
    P
    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &a, int target) {
            int m = a.size();
            if (m==0) return false;
            int n = a[0].size();
            return helper(a,0,m-1,0,n-1, target);
        }
        
        bool helper(vector<vector<int> > &a, int lr,int hr, int lc, int hc, int target) {
            if (lr > hr || lc > hc || target < a[lr][lc] || target > a[hr][hc]) return false;
            int mr = (lr+hr)/2;
            int mc = (lc+hc)/2;
            if (a[mr][mc] == target) return true;
            if (a[mr][mc] > target) {
                return helper(a,lr,mr,lc,mc,target) || helper(a,lr,mr-1,mc+1,hc,target);
            } else {
                return helper(a,mr+1,hr,lc,mc,target) || helper(a,mr,hr,mc+1,hc,target);
            }
        }
    };

  • 0
    O

    To do a binary search for the whole matrix is brilliant. But actually you can do some tricks to each sub vector. Because you can only compare the head and tail of each sub vector with the target, to judge if use a binary_search for the whole sub vector.
    I use this method which took 1 ms less than yours : )


Log in to reply
 

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