Search a 2D Matrix

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 from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Naive Way: There lies a linear approach O(n+m).

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

The idea is to start from upper right. If current number is larger than target, that means you cannot find target in current row. So turn to next row. If current number is smaller than target, that means the target must lie in current row.

Improved Way: Could use a binary search approach to search current row/column. Speed up the approach to O(logn + logm) = O(log(nm))

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int row = binarySearch(matrix, target);  
     if(row==-1) return false;  
     int col = binarySearch(matrix[row], target);  
     return col!=-1;  
   }  
   private int binarySearch(int[][] matrix, int target){  
     int low = 0, high = matrix.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(matrix[middle][0] <= target && middle==matrix.length-1) return middle;  
       if(matrix[middle][0] <= target && matrix[middle+1][0] > target) return middle;  
       if(matrix[middle][0] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return low;  
   }  
   private int binarySearch(int[] array, int target){  
     int low = 0, high = array.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(array[middle] == target) return middle;  
       if(array[middle] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return -1;  
   }  
 }  

Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Naive Way: Return the square root of an integer as an integer. I use binary search. First I need to find maximum possible square root, which is (int)Math.sqrt(Integer.MAX_VALUE). And when it happens sqrt(x) is this value, can't use i^2 <= x <(i+1)^2 to end the loop since (i+1)^2 will overflow. List this case separately.

 public class Solution {  
   static final int MAX_SQRT = (int)Math.sqrt(Integer.MAX_VALUE);  
   public int sqrt(int x) {  
     int high = MAX_SQRT, low = 0;  
     while(low <= high){  
       int middle = (high+low)/2;  
       if(middle*middle <= x && middle == MAX_SQRT) return middle;  
       if(middle*middle <= x && (middle+1)*(middle+1) > x) return middle;  
       if(middle*middle > x)  
         high = middle-1;  
       else  
         low = middle+1;  
     }  
     return low;  
   }  
 }  

Improved Way: There is a mathematical method Newton's Method. I can't understand what is stated in the link. There are too mathematical. I understand from other one's algorithm newtons-iterative-method-in-c . In the answer of that question. Newton's method was explained.