[C/LeetCode] Search a 2D Matrix

Daily LeetCoding Challenge March, Day 30

 

문제: 2 dimension matrix 안에 target number 존재 유무 bool return 하기

이때 2차원 matrix의 특징

- 각 row는 오름차순

- next row first column value > previous row last column value

 

아이디어: Binary Search + Brute Force in row search

row를 반복문으로 돌면서 첫 번째 value와 값을 비교하고 같으면 return,

value > target 인 경우 이전 row에 대해서 값이 있거나 없다는 뜻이므로 그때 binary search 진행

 

예외 처리: last row

마지막 row는 반복문에 걸리지 않기 때문에 반복문 탈출 후 마지막 row에 대해서 binary search 진행

 

완성

submission: 6ms / 6.1MB (less than 99%)

bool BinarySearch(int* nums, int numsSize, int target){
    int start = 0;
    int end = numsSize - 1;
    int mid;
    
    if (nums[start] == target || nums[end] == target)
        return true;
        
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (nums[mid] == target)
            return true;
        else if (nums[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    
    return false;
}

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    for(int start = 1;start < matrixSize;start++)
    {
        if (matrix[start][0] == target)
            return true;
        else if (matrix[start][0] > target)
            return BinarySearch(matrix[start - 1], *matrixColSize, target);
    }
    return BinarySearch(matrix[matrixSize - 1], *matrixColSize, target);
}

 

단점

일단 메모리 효율을 좋게 짜긴 했지만 더 좋은 코드가 있을 것 같다.

지금 떠오르는 생각으론, matrix row마다 첫번째 값들도 정렬이 되어 있는 상태이니까 이 값만 따로 binary search든 뭐든 사용해서 특정 행을 찾은 다음에 바로 binary search 돌리면 되니까 시간 단축이 될 듯하다.