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

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

 

주어진 숫자 2D Matrix에서 대상 target이 존재하는지 여부를 반환하라.

 

2가지 방법으로 풀수 있다. 

우선 1열의 값들로 대상값을 비교해 찾거나 아니면 target이 이전 열보다 크고 현재보다 작은지 찾는다.

그러면 대상 행이 나오고 이 행에서 역시 같은 방법으로 binary search를 한다. 

 

아니면, 

전체 matrix를 1차원 index로 변환해서 한번에 binary search를 해도 된다. 

 

두번째 방법이 더 심플해 보여 코드를 만든다.

 

코드 

bool searchMatrixBS(vector<vector<int>>& matrix, int left, int right, int target)
{
    if (left > right)    return false;

    int H = matrix.size();
    int W = matrix[0].size();

    int mid = left + (right - left) / 2;
    int iy = mid / W;
    int ix = mid % W;

    if (matrix[iy][ix] == target)
        return true;
    else if(matrix[iy][ix] > target)
        return searchMatrixBS(matrix, left, mid-1, target);
    else 
        return searchMatrixBS(matrix, mid+1, right, target);
}

bool searchMatrix(vector<vector<int>>& matrix, int target) 
{
    return searchMatrixBS(matrix, 0, matrix.size() * matrix[0].size() - 1, target);
}

 

결과