LeetCode 74 - Search a 2D Matrix

Search a 2D Matrix - LeetCode

 

m x n 2차원 배열인 matrix에 target에 존재하는지 확인하는 문제이다.

matrix에는 특징이 있는데 각각의 row는 오름차순으로 정렬 돼 있고 각 row의 첫 번째 값은 이전 row의 마지막 값보다 크다.

O(log(m*n))의 시간 복잡도로 해결해야 한다.

matrix의 조건을 보면 알 수 있듯이 결국 정렬된 상태라는 소리다.

flatMap으로 1차원으로 변경할 수 있으면 좋지만 시간복자도 제한 때문에 불가능하다. 그렇지만 이미 정렬된 상태이기 때문에 2D인 채로 이진 탐색이 가능하다.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        return binarySearch(matrix, 0, m * n - 1, target, m, n) < 0 ? false : true;
    }

    private int binarySearch(int[][] arr, int left, int right, int target, int m, int n) {
        if (left > right) return -1;

        int mid = left - (left - right) / 2;
        int value = arr[mid / n][mid % n];

        if (value == target) {
            return mid;
        } else if (value < target) {
            return binarySearch(arr, mid + 1, right, target, m, n);
        } else {
            return binarySearch(arr, left, mid - 1, target, m, n);
        }
    }
}