Three binary search solution Java


  • 0
    J

    Do three binary search: first row, then a column, then row again

       public class Solution {
          public boolean searchMatrix(int[][] matrix, int target) {
              if (matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0) return false;
        
              int rows = matrix.length;
              int cols = matrix[0].length;
        
              int c = Arrays.binarySearch(matrix[0], target);
              if (c>=0) return true;
              c = -(c+1)-1;
              if (c<0) return false;
              int[] colArr = getCol(matrix, c);
              int r = Arrays.binarySearch(colArr, target);
              if (r>=0) return true;
              r = -(r+1);
              if (r==rows) return false;
              c = Arrays.binarySearch(matrix[r], target);
              return c>=0;
    }
    
          private int[] getCol(int[][] matrix, int c) {
              // get the column at index c as 1d array
              int[] colArr = new int[matrix.length];
              for (int i=0; i<matrix.length; ++i) {
              colArr[i] = matrix[i][c];
          }
          return colArr;
    }
    

    }


Log in to reply
 

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