Search a 2D matix

Problem:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Solution:


class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool sol;
        int col = matrix.size();
        int row = matrix[0].size();
       
        if (matrix[0][0] > target || matrix[col - 1][row - 1] < target) {
            return false;
        }
       
        int col_start = 0, col_end = col - 1, col_index;
       
        while (col_start <= col_end) {
            col_index = (col_start + col_end) / 2;
           
            if (matrix[col_index][0] == target) {
                return true;
            } else if (col_index != 0 && matrix[col_index][0] > target) {
                    if (matrix[col_index - 1][0] == target) {
                        return true;
                    }
                    else if (matrix[col_index - 1][0] < target) {
                        return search(matrix[col_index - 1], row, target);
                    } else {
                        col_end = col_index - 1;
                    }
            } else if ((col_index != col - 1) && matrix[col_index][0] < target ) {
                    if (matrix[col_index + 1][0] == target) {
                        return true;
                    }
                    else if (matrix[col_index + 1][0] > target) {
                        return search(matrix[col_index], row, target);
                    } else {
                        col_start = col_index + 1;
                    }
            } else {
                // When only one row is there, then both above else-if fails.
                return search(matrix[col_index], row, target);
            }
        }

        return false;
    }
   
    bool search(vector<int> &row_mat, int row, int target) {
        int beg = 0, end = row - 1, index;
        //return false;
        if (row_mat[row - 1] < target)
            return false;

        while (beg <= end) {
            index = (beg + end)/2;
            if (row_mat[index] == target) {
                return true;
            } else if (row_mat[index] > target) {
                end = index - 1;
            } else {
                beg = index + 1;
            }
        }
        return false;
    }
};