[algo/neetcode] search a 2D matrix

문제 링크

---

코드 잘못쓴 부분

풀이로직이 아닌 TypeError 와 같이 언어 잘못 쓴 경우

class Solution {

public:

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        return binary_search(matrix.begin(), matrix.end(), target);

    }

};

컴파일 에러 뜨는 이유

• std::binary_search(first, last, value) : 범위 안의 원소들과 value를 직접 비교함(<)
• matrix.begin()~matrix.end()는 vector<int>를 원소로 가짐
• target은 int
• vector<int> < int 비교를 하게 되므로 타입이 맞지 않음 → 연산 X → 컴파일 에러
• 해결 : 각 행에 대해 binary search 적용하기

---

최종 코드 (STL 사용)

class Solution {

public:

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        for (vector<int>&rows : matrix) {

            if (binary_search(rows.begin(), rows.end(), target)) {

                return true;

            }

        }

        return false;

    }

};

---

STL 사용하지 않고 구현

class Solution {

public:

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        auto len = matrix[0].size();

        for (vector<int>&rows : matrix) {

            int st = 0, en = len-1;

            while (st < en) {

                int mid = (st + en) / 2;

                if (rows[mid] < target) st = mid + 1;

                else if (rows[mid] > target) en = mid - 1;

                else return true;

            }

        }

        return false;

    }

};