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 && lastCol>=0){
        if(matrix[row][lastCol]==target){
            return true;
        }
        if(matrix[row][lastCol]>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(lowtarget){
            high = mid-1;
        }
    }
    return -1;
}

Space complexity = \$\mathcal{O}(1)\$

Time Complexity = \$\mathcal{O}(\log(n!))\$

Your algorithm is not efficient (that's the brutal part of the answer).

Searching in a list of t values is a task that can be accomplished using \$\mathcal{O}(\log(t))\$ comparisons. Here we have \$t=mn\$ values so it should be accomplished using \$\mathcal{O}(\log(mn)) = \mathcal{O}(\log(m))+\mathcal{O}(\log(n))\$ comparisons. I suspect your algorithm may execute the while loop about matrix.length times so it is not \$\mathcal{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 searched value.

• If the value found matches, 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.

Another 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 erroneous implementation of the binary search even in the JDK.

StackExchange Code Review Q#45783, answer score: 2