Leetcode 240 Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Solution 1: Use binary search, 4 dimension, each time remove half of the 2-D array.

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     int m=matrix.length;  
     if (m==0) return false;  
     int n=matrix[0].length;  
     int xLo=0, yLo=0, xHi=n-1, yHi=m-1;  
     while (xLo<=xHi && yLo<=yHi) {  
       int i=xLo, j=xHi;  
       while (i<=j) {  
         int mid=i+(j-i)/2;  
         if (matrix[yLo][mid]==target) return true;  
         else if (matrix[yLo][mid]>target) j=mid-1;  
         else i=mid+1;  
       }  
       xHi=j;  
       i=yLo; j=yHi;  
       while (i<=j) {  
         int mid=i+(j-i)/2;  
         if (matrix[mid][xLo]==target) return true;  
         else if (matrix[mid][xLo]>target) j=mid-1;  
         else i=mid+1;  
       }  
       yHi=j;  
       i=xLo; j=xHi;  
       while (i<=j) {  
         int mid=i+(j-i)/2;  
         if (matrix[yHi][mid]==target) return true;  
         else if (matrix[yHi][mid]>target) j=mid-1;  
         else i=mid+1;  
       }  
       xLo=i;  
       i=yLo; j=yHi;  
       while (i<=j) {  
         int mid=i+(j-i)/2;  
         if (matrix[mid][xHi]==target) return true;  
         else if (matrix[mid][xHi]>target) j=mid-1;  
         else i=mid+1;  
       }  
       yLo=i;  
     }  
     return false;  
   }  
 }  

Solution 2: Start at top right corner, if the target>nums[i][j], means entire row can be exclude, moving down, if target<nums[i][j], the enter column can be exclude moving left. O(m+n) solution.

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     int m=matrix.length;  
     if (m==0) return false;  
     int n=matrix[0].length;  
     int i=0, j=n-1;  
     while (i<m && j>=0) {  
       if (matrix[i][j]<target) i++;  
       else if (matrix[i][j]>target) j--;  
       else return true;  
     }  
     return false;  
   }  
 }