Two Short Binary Search Solutions In Javascript.


  • 0

    Many people share their solutions already but I didn't see too many js ones so here is my shoot.

    Soluton 1: Treat this 2d matrix as a long array.

    Think there is an array built from the matrix, then there will be m*n elements, and each index can traced back to the matrix's indexes. so each time when calculate mid, turn it to the correct ones of the matrix.

    /**
     * Memo: Use BS to search, just need to calculate the index into a 2d array. Note that for matrix[i,j], it is (i-1)*n+j th element
     * Complex: O(log(mn))
     * Runtime: 125ms
     * Tests: 134 test cases passed
     * Rank: S
     */
    var searchMatrix = function(matrix, target) {
        var m = matrix.length;
        var n = matrix[0].length;
    
        var start = 0;
        var end = m * n - 1;
        var mid = 0;
        while (start <= end) {
            mid = ~~((start + end) / 2);
            var i = ~~((mid / n));
            var j = mid - i * n;
            if (matrix[i][j] === target) return true;
            matrix[i][j] < target ? start = mid + 1 : end = mid - 1;
        }
        return false;
    };
    

    Solution 2: Locate which row the target might be in first.

    As the matrix is already sorted, the first element of each row is also sorted as well, so it will be easy to locate which row the target might be in first, then check that row to see whether the target is really inside or not.

    /**
     * Memo: First using binary search to find which row the result might be in, then use binary search to see if the target is in that row.
     * Complex: O(logm + logn)
     * Runtime: 130ms
     * Tests: 134 test cases passed
     * Rank: S
     * Updated: 2015-06-28
     */
    var searchMatrix = function(matrix, target) {
        var m = matrix.length;
        var n = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;
    
        var start = 0;
        var end = m - 1;
        var mid = 0;
        while (start <= end) {
            mid = ~~((start + end) / 2);
            if (matrix[mid][0] === target) return true;
            matrix[mid][0] > target ? end = mid - 1 : start = mid + 1;
        }
    
        var row = start - 1;
        start = 0;
        end = n - 1;
    
        while (start <= end) {
            mid = ~~((start + end) / 2);
            if (matrix[row][mid] === target) return true;
            matrix[row][mid] > target ? end = mid - 1 : start = mid + 1;
        }
        return false;
    };
    

    PS: Even though the solution 2 should be faster in theory, the actually result is solution 1 is a bit faster. Probably the test case is not that large I guess.


  • 0
    R

    Another binary search solution in JS:

    var searchMatrix = function(matrix, target) {
        if (!matrix || matrix.length < 1 || matrix[0].length < 1) return false;
            var row_num = matrix.length;
            var col_num = matrix[0].length;
            
            var begin = 0, end = row_num * col_num - 1;
            
            while(begin <= end) {
                var mid = (begin + (end - begin) / 2)>>0;
                var mid_value = matrix[(mid/col_num)>>0][mid%col_num];
                
                if(mid_value == target) { 
                    return true;
                } else if (mid_value < target) {
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return false;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.