# LeetCode: Search A 2d Matrix II Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}function binarySearch(A, k) {2  const N = A.length3  let begin = 04  let end = N - 15  while (begin <= end) {6    let mid = Math.floor((begin + end) / 2)7    if (A[mid] === k) {8      return true9    } else if (A[mid] > k) {10      end = mid - 111    } else if (A[mid] < k) {12      begin = mid + 113    }14  }15  return false16}17
18/**19 * @param {number[][]} matrix20 * @param {number} target21 * @return {boolean}22 */23// O(m * logn)24var searchMatrix = function (matrix, target) {25  let m = matrix.length26  let n = matrix[0].length27  let res = false28
29  for (let i = 0; i < m; i++) {30    const arr = matrix[i]31    if (binarySearch(arr, target)) {32      res = true33    }34  }35
36  return res37}38
39// O(m + n)40var searchMatrix = function (matrix, target) {41  let m = matrix.length42  let n = matrix[0].length43  let i = 044  let j = n - 145
46  while (j >= 0 && i < m) {47    if (matrix[i][j] === target) {48      return true49    } 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 false59}```

leetcode

binary search

## Next Post

LeetCode: Score Of Parentheses

Feb 24, 2021

Search Posts