LeetCode: Search A 2d Matrix II Solution

1function binarySearch(A, k) {
2  const N = A.length
3  let begin = 0
4  let end = N - 1
5  while (begin <= end) {
6    let mid = Math.floor((begin + end) / 2)
7    if (A[mid] === k) {
8      return true
9    } else if (A[mid] > k) {
10      end = mid - 1
11    } else if (A[mid] < k) {
12      begin = mid + 1
13    }
14  }
15  return false
16}
17
18/**
19 * @param {number[][]} matrix
20 * @param {number} target
21 * @return {boolean}
22 */
23// O(m * logn)
24var searchMatrix = function (matrix, target) {
25  let m = matrix.length
26  let n = matrix[0].length
27  let res = false
28
29  for (let i = 0; i < m; i++) {
30    const arr = matrix[i]
31    if (binarySearch(arr, target)) {
32      res = true
33    }
34  }
35
36  return res
37}
38
39// O(m + n)
40var searchMatrix = function (matrix, target) {
41  let m = matrix.length
42  let n = matrix[0].length
43  let i = 0
44  let j = n - 1
45
46  while (j >= 0 && i < m) {
47    if (matrix[i][j] === target) {
48      return true
49    } else if (matrix[i][j] < target) {
50      // can't be at the current col so:
51      i++
52    } else if (matrix[i][j] > target) {
53      // can't be at the current row so:
54      j--
55    }
56  }
57
58  return false
59}