C# O(m+n) recursive binary search


  • 0
    S

    The idea is very simple. You start from the top right corner. If the target is greater than the top right corner value, then it can't be in entire row, hence you move on to the next row. If the target is smaller, it means it can't be in that specific column; therefore, you decrement column.

    public class Solution {
        public bool SearchMatrix(int[,] matrix, int target) {
            return SearchMatrixHelper(matrix, target, 0, matrix.GetUpperBound(1));
        }
        
        public bool SearchMatrixHelper(int [,] matrix, int target, int rows, int columns){
            if (rows > matrix.GetUpperBound(0) || columns > matrix.GetUpperBound(1) || rows < 0 || columns < 0){
                return false;
            }
            
            if (matrix[rows, columns] == target){
                return true;
            }
            
            if (target > matrix[rows,columns]){
                return SearchMatrixHelper(matrix, target, rows + 1, columns);
            }else{
                return SearchMatrixHelper(matrix, target, rows, columns - 1);
            }
        }
    }
    

Log in to reply
 

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