LeetCode 240 - Search a 2D Matrix II (Medium)

문제

LeetCode - 155번

풀이 과정

이차원 배열에서 목표값이 존재하는지 판단하는 문제입니다.

그냥 브루트 포스 로 접근한다면 O(MN) 의 시간 복잡도로 해결할수도 있지만
좀 더 효율적인 탐색을 위해 이분 탐색 을 적용했습니다.

각 행이 오름차순으로 정렬되어 있다는 점을 이용해서 각 행마다 이분 탐색 을 수행해 원하는 값이 존재하는지 판단합니다.

코드

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  for (let row of matrix) {
    if (bisect(row, target)) return true;
  }

  return false;
};

function bisect(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    let mid = Math.floor((lo + hi) / 2);

    if (arr[mid] === target) return true;
    else if (arr[mid] > target) hi = mid - 1;
    else lo = mid + 1;
  }

  return false;
}