My C# O(log(n) + log(m)) solution with explanation.


  • 0
    A
    public bool SearchMatrix(int[,] matrix, int target) {
        int row = FindRow(matrix,target);
        if (row == -1)
            return false;
        int l = 0, r = matrix.GetLength(1) - 1;
        int mid;
        while(r >= l) {
            mid = (r - l) / 2 + l;
            if (target == matrix[row, mid])
                return true;
            else if (target < matrix[row, mid])
                r = mid - 1;
            else if (target > matrix[row, mid])
                l = mid + 1;
        }
        return false;
    }
    
    private int FindRow(int[,] matrix, int target) {
        int l = 0, r = matrix.GetLength(0) - 1;
        int mid;
        while (r >= l) {
            mid = (r - l) / 2 + l;
            if (target >= matrix[mid,0] && target <= matrix[mid,matrix.GetLength(1) - 1])
                return mid;
            else if (target < matrix[mid,0])
                r = mid - 1;
            else if (target > matrix[mid, matrix.GetLength(1) - 1])
                l = mid + 1;
        }
        return -1;
    }
    

    The basic idea is next: firstly with a binary search find a row which could contain
    the target (row[0] <= target and row[lenght - 1] >= target) and search in this row for our target.


Log in to reply
 

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