Leetcode 74 Solution

This article provides solution to leetcode question 74 (search-a-2d-matrix)
Categories:
Tags:
Access this page by simply typing in "lcs 74" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
    int bsearch(const vector<int>& a, int target)
    {
        int l = 0;
        int r = a.size() - 1;

        while (l <= r)
        {
            int m = (l + r) / 2;

            if (target < a[m])
                r = m - 1;
            else
                l = m + 1;
        }

        return r;
    }

public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return false;

        vector<int> a;

        for(int i = 0; i < matrix.size(); i++)
            a.push_back(matrix[i][0]);

        int row = bsearch(a, target);

        if (row == -1)
            return false;

        int col = bsearch(matrix[row], target);

        if (col < matrix[row].size())
            return matrix[row][col] == target;
        else
            return false;
    }
};