LeetCode Search a 2D Matrix (JavaScript), Binary Search

링크 : https://leetcode.com/problems/search-a-2d-matrix/description/

문제 설명

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• 104 <= matrix[i][j], target <= 104

---

문제 풀이

접근 방식

1. target이 어떤 행에 속해있는지 구하기 (index)
2. 문제에 포함 여부를 판단하는 시간 복잡도가 O(log(m * n))의 시간 복잡도를 가져야 함 -> 일반적인 탐색으로는 불가 -> Binary Search 이용

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let index = -1;
    for (let i = 0; i < matrix.length; i++) {
        if (matrix[i][0] <= target && target <= matrix[i][matrix[0].length - 1]) {
            index = i;
            break;
        }
    }

    if (index === -1) {
        return false;
    }

    if (index !== -1 && matrix[index].length === 1) {
        return true;
    }

    let [left, right] = [0, matrix[0].length - 1];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (matrix[index][mid] === target) {
            return true;
        }

        if (target < matrix[index][mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
};

---

결론

주어진 O(log(m * n))의 시간 복잡도로 해결하기 위해 이분탐색을 이용하여 특정 숫자를 찾는 문제.