C# solution using binary search


  • 0
    K
    public class Solution {
        public bool SearchMatrix(int[,] matrix, int target) {
            
            int numrows = matrix.GetLength(0);
            int numcols = matrix.GetLength(1);
            
            int first = 0;
            int last = numrows - 1;
            int mid = 0;
            int rowpos = -1;
            // first find the row which the target belongs to
            while (first <= last) {
                mid = (first+last)/2;
                if (matrix[mid,numcols-1] == target) {
                    rowpos = mid;
                    break;
                }
                else if (matrix[mid,numcols-1] < target )
                    first = mid + 1;
                else
                    last = mid - 1;
            }
            if (rowpos == -1) rowpos = first;
            if (rowpos > numrows-1) return false;
            // then search the target in that row
            first = 0;
            last = numcols - 1;
            while (first <= last) {
                mid = (first+last)/2;
                if (matrix[rowpos,mid] == target)
                    return true;
                else if (matrix[rowpos,mid] < target )
                    first = mid + 1;
                else
                    last = mid - 1;
            }        
            return false;
        }
    }
    

Log in to reply
 

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