[Binary Search][Medium] 74. Search a 2D Matrix

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

Search a 2D Matrix - LeetCode

 

Q. 주어진 matrix가 좌에서 우로, 상에서 하로 오름차순 정렬되어 있다. 

 각 row의 첫째 값은 이전 줄의 마지막 값보다 늘 크다. 

 이때 target value가 matrix에 존재 하는지 여부를 찾아 반환하라. 

 

 

 

Solution. 

 딱히 어려운건 없어 보인다. 

 다만 row, col의 2중 search를 하면 되겠다.

 

 먼저 col 을 찾고 해당 열에서 값을 조회하는 전략을 취하면 될 것이다. 

 다만 col 이 하나만 있을때 예외 처리에 유의한다. 

 

 간단하므로 바로 코드를 작성해 본다. 

 

 

int searchCol(vector<vector<int>>& matrix, int target, int left, int right)
{
    // 겹쳐질때, 작은 값을 반환하되, 범위 안에 들도록 반환한다.
    if(left > right)  
        return clamp(right, 0, (int)matrix.size()-1);

    int mid = left + (right-left) / 2;

    if(matrix[mid][0] == target) return mid;
    else if(matrix[mid][0] > target) return searchCol(matrix, target, left, mid-1);
    else return searchCol(matrix, target, mid+1, right);
}
int searchValue(vector<int>& nums, int target, int left, int right)
{
    if(left > right) return -1;

    int mid = left + (right-left) / 2;

    if(nums[mid] == target) return mid;
    else if(nums[mid] > target) return searchValue(nums, target, left, mid-1);
    else return searchValue(nums, target, mid+1, right);
}

bool searchMatrix(vector<vector<int>>& matrix, int target) 
{
    int col = searchCol(matrix, target, 0, matrix.size()-1);
    return searchValue(matrix[col], target, 0, matrix[col].size()-1)!=-1;
}

 

적합한 결과를 얻었다.