Searching a 2D Sorted Matrix (1) - JavaScript

Question

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]

Origin from: LeetCode


Solution

// Time complexity: O(n+m)
function findElement(arr, num) {
    var m = arr.length,
        n = arr[0].length,
        row = 0,
        col = n - 1;

    if (num < arr[0][0] || num > arr[m - 1][n - 1]) {
        return false;
    }

    while (row <= (n - 1) && col >= 0) {
        if (arr[row][col] < num) {
            row++;
        } else if (arr[row][col] > num) {
            col--;
        } else {
            console.log(row + " " + col);
            return true;
        }
    }
    return false;
}

var arr = [
    [1, 2, 3, 4, 5],
    [6, 7, 8, 9, 10],
    [11, 12, 13, 14, 15],
    [16, 17, 18, 19, 20],
    [21, 22, 23, 24, 25]
];
findElement(arr, 16); // 3 0
findElement(arr, 23); // 4 2
findElement(arr, 9); // 1 3

Demo

Yang Zhao

Read more posts by this author.


Comment