6
\$\begingroup\$

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(low<=high){
        int mid = (low + high)/2;
        if(arr[mid]==target){
            return mid;
        }
        else if(arr[mid]<target){
            low = mid+1;
        }
        else if(arr[mid]>target){
            high = mid-1;
        }
    }
    return -1;
}

Space complexity = O(1) Time Compexity = O(log(n!))

\$\endgroup\$
  • 1
    \$\begingroup\$ A better way to do this is to treat it like a single dimension sorted array, and perform your binary search on that, using modulo and division to extract your values from the 2d array. \$\endgroup\$ – Azar Mar 31 '14 at 1:55
  • \$\begingroup\$ Can you explain how I'd use modulo, a bit weak with that operation. \$\endgroup\$ – bazang Mar 31 '14 at 2:05
  • \$\begingroup\$ something like row = mid/ arr[0].length() and col = mid % arr[0].length(). If no-one else does, I'll post an answer tomorrow, but I need to get some sleep. \$\endgroup\$ – Azar Mar 31 '14 at 2:10
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Really not more complicated at all, but yes, it has the same runtime, O(log(mn)). \$\endgroup\$ – Azar Mar 31 '14 at 10:17
  • \$\begingroup\$ @Azar: If it is not more complicated I am curious about your answer. \$\endgroup\$ – miracle173 Mar 31 '14 at 16:06
  • \$\begingroup\$ Sorry, been a little busy lately. Here you go: pastebin.com/t59ZnJFQ \$\endgroup\$ – Azar Apr 2 '14 at 1:10
  • \$\begingroup\$ @Azar: The overhead is insignificant so I will remove the recommendation from my posting. You avoided the mentioned bug. Nevertheless I would recommand to use a library. \$\endgroup\$ – miracle173 Apr 4 '14 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.