Leetcode - 240. Search a 2D Matrix II

문제

행과 열이 모두 오름차순 정렬된 MxN크기의 matrix가있다. target값이 존재하면 true 없으면 false를 리턴.

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 
target = 5
Output: true

https://leetcode.com/problems/search-a-2d-matrix-ii/

해결 O(MlogN)

binary search를 행과 열 모두 할필요가 없고, 행을 순회하면서만 함. 추가 개선 포인트로, 모든 행을 탐색할필요가 없음.

• target이 행의 [0]인덱스 값보다 작으면 더이상 다음 행을 순회할 필요 없음.
• target이 행이 마지막 인덱스 값보다 크면 현재 행을 탐색할 필요 없음.

크기가 MxN(행x열) 시간복잡도는 O(MlogN)

int bin_search(int *arr, int size, int tgt)
{
    int left = 0, right = size - 1, mid = 0;
    
    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] == tgt)
            return mid;
        else if (arr[mid] < tgt)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    for (int i = 0; i < matrixSize; i++) {
        if (target < matrix[i][0])
            break;
        if (target > matrix[i][*matrixColSize - 1])
            continue;
        if (bin_search(matrix[i], *matrixColSize, target) != -1)
            return true;
    }
    return false;
}

해결 O(M + N)

solution에서 천재적 아이디어 발견. binary search할 필요없이 리니어하게 탐색이 가능. 시작 포인트를 matrix의 맨 좌-하단에서 시작하고, target이 더 작으면 한칸 위로, target이 더 크면 한칸 우측으로 이동하며 값을 비교한다.

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int row = matrixSize - 1;
    int col = 0;
    
    while (row >= 0 && col < *matrixColSize) {
        if (matrix[row][col] == target) {
            return true;
        } else if (target < matrix[row][col]) {
            row--;
        } else {
            col++;
        }
    }
    return false;
}