Seems the binary search is not helpful for rows?the time of this result is 12ms


  • 0
    L

    class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int k=0;
        for(int x=0;x<matrix.size();x++){
            if(matrix[0][0]>target){
                return false;
            }
           else if(matrix[x][0]==target)
                  return true;
          else if((x==matrix.size()-1)||(matrix[x][0]<target&&(matrix[x+1][0]>target))){
                     k=x;
                     break;}
                 }   
    
      for(int low=0,high=matrix[0].size()-1,mid=0;low<=high;mid=(low+high)/2){
              if(matrix[k][mid]==target)
                    return true;
              else
                    if(matrix[k][mid]<target){
                        low=mid+1;}
                    if(matrix[k][mid]>target){
                        high=mid-1;}
             }
             return false;
             
         
    }
    

    };


  • 0
    P

    You cannot do better than O(log(m) + log(n)).
    Your code will run faster if you use binary search to find row as well. You can first find the row and then look for the element in the chosen column. It will require 2 loops. But you are a fan of concise code (complexity being the same in both cases), I suggest you assume the entire 2d vector to be a 1d vector of m*n sorted elements and use binary search on it instead.

    I hope it helped.


  • 0
    L

    very thank you!


Log in to reply
 

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