Another method using binary search and recursive, the avg performance is better then the normal one.


  • 0
    P
    public class Solution {
        int rows=0,cols=0;
        public bool SearchMatrix(int[,] matrix, int target) {
            if(matrix == null)
                return false;
            rows = matrix.GetLength(0);
            cols = matrix.GetLength(1);
            if(rows * cols == 0)
                return false;
            return Search(matrix,target,0,rows -1,0,cols - 1);   
        }
        
        bool Search(int[,] matrix, int target,int rl,int rh,int cl,int ch) {
            
            if(rl > rh || cl > ch)
                return false;
            if(rl == rh && cl == ch)
                return matrix[rl,cl] == target;
            if(matrix[(rl+rh)/2,(cl+ch)/2] < target)
                return Search(matrix,target,(rl+rh)/2+1,rh,cl,ch) || Search(matrix,target,rl,(rl+rh)/2,(cl+ch)/2+1,ch);
            else if(matrix[(rl+rh)/2,(cl+ch)/2] > target)
                return Search(matrix,target,rl,(rl+rh)/2-1,cl,ch) || Search(matrix,target,(rl+rh)/2,rh,cl,(cl+ch)/2-1);
            else
                return true;
        }
    

    }


Log in to reply
 

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