Search2DMatrix.java

import java.util.Arrays;
public class Search2DMatrix{
    public boolean searchMatrixOne(int[][] matrix, int target){
        int numOfRows = matrix.length;
        int numOfColumns = matrix[0].length;
        
        if (numOfRows == 0 || numOfColumns == 0) return false;
        
        // here we assume that the total number of elements in the matrix 
        // is inside the range of Integer in Java
        int total = numOfRows * numOfColumns;
        // then we treat the matrix as a large one-dimensional array and do a binary search
        int low = 0;
        int high = total - 1;
        while (low <= high){
            int mid = (low + high) / 2;
            // now locate the element in the matrix indicated by mid
            // better to draw a picture of a simple matrix
            int numAtMid = matrix[mid/numOfColumns][(mid%numOfColumns)];
            if (target == numAtMid) return true;
            if (target > numAtMid){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return false;
    }
    
    public boolean searchMatrixTwo(int[][] matrix, int target){
        // in case m*n is greater than the limit of Java Integer
        int numOfRows = matrix.length;
        int numOfColumns = matrix[0].length;
        
        if (numOfRows == 0 || numOfColumns == 0) return false;
        // use the first pass to get the possible row that the target could reside
        int low = 0;
        int high = numOfRows - 1;
        int rowInd = -1;
        while(low < high){
            int mid = (low + high) / 2;
            if (target >= matrix[mid][0] && target < matrix[mid+1][0]){
                rowInd = mid;
                break;
            }else if(target < matrix[mid][0]){
                high = mid - 1;
            }else if(target >= matrix[mid+1][0]){
                low = mid + 1;
            }
        }
        if (low == high) rowInd = low;
        if (high < 0) return false; // this is a tricky boundary case matrix: [[1]] and target: 0
        return Arrays.binarySearch(matrix[mid], target) >= 0;
    }
}