Searching in a sorted 2D matrix If I was at an interview, and wrote this code, what would you think? Please be brutal.

Time it took to wrote it: 13 minutes

Problem:


  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.




 public boolean searchMatrix(int[][] matrix, int target) {
    int lastCol = matrix[0].length-1;
    int row=0;
    while(row!=matrix.length &amp;&amp; lastCol&gt;=0){
        if(matrix[row][lastCol]==target){
            return true;
        }
        if(matrix[row][lastCol]&gt;target){
            lastCol--;
            if(binarySearch(matrix[row], 0, lastCol, target)!=-1){
                return true;
            }
        }
        row++;
    }
    return false;
}
public int binarySearch(int[] arr, int low, int high, int target){
    while(low&lt;=high){
        int mid = (low + high)/2;
        if(arr[mid]==target){
            return mid;
        }
        else if(arr[mid]&lt;target){
            low = mid+1;
        }
        else if(arr[mid]&gt;target){
            high = mid-1;
        }
    }
    return -1;
}


Space complexity = O(1)
Time Compexity = O(log(n!))
Your algorithm is not efficient (thats the brutal part of the answer).

Searching in a list of  t values is a task that can be accomplished using O(log(t)) comparisons. Here we have t=m*n values so it should be accomplished using O(log(m*n)) = O(log(m))+O(log(n)) comparisons. I suspect your algorithm may execute the while loop about matrix.length times so it is not O(log(m)) (where m is the number of rows). 

The algorithm could work in the following way:


if the searched value is smaller then the first column in the first row then the searched value is not contained in the matrix.
Then do a binary search on the first column of the matrix to find the largest  entry smaller or equal to the searchd value
if the value found macthes you are done. 
otherwise do a binary search on the row found. 
if the value found matches the searched value you are done
otherwise the searched value is not in the matrix


Annother way is to treat the problem like a single dimension sorted array as it is proposed in the comment of @Azar. 

Even a small piece of code can have a lot of errors so it does make sense to try to use library methods to accomplish this task and not implement the binary search by yourself (but I don't know if this is the intention of the poser of the problem).

This blog entry discusses an example of a buggy implementation in Java. It references the following SUN  bug report because there was an errornous implementation of the binary search even in the JDK.