[Binary Search] Search a 2D Matrix

74. Search a 2D Matrix

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 
 * Runtime	: 61 ms
 * Memory	: 42.00 MB
 */
var searchMatrix = function(matrix, target) {
  for(const nums of matrix) {
    if(searchBinary(nums, target)) {
      return true;
    }
  }

  return false;
};

var searchBinary = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let mid = null;

  while (left <= right) {
    mid = Math.round((left + right) / 2);

    if (nums[mid] == target) {
        return true;
    } else if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
  }
  
  return false;
}

직전 문제 [Binary Search] Search Insert Position의 제출 함수를 그대로 활용한 해답입니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Treating the Matrix as a 1-Dimensional Array

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 51 ms
 * Memory	: 42.16 MB
 */
var searchMatrix = function(matrix, target) {
  let m = matrix.length;
  let n = matrix[0].length;
  let left = 0, right = m * n - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let mid_val = matrix[Math.floor(mid / n)][mid % n];

    if (mid_val === target)
        return true;
    else if (mid_val < target)
        left = mid + 1;
    else
        right = mid - 1;
  }
  return false;
};

본 해답은 다음과 같은 문제의 특징을 이용하여 2차원 배열을 1차원 배열처럼 다루었습니다.

1. 각 행은 감소하지 않는 순서로 정렬됩니다.
2. 각 행의 첫 번째 정수가 이전 행의 마지막 정수보다 큽니다.