# 240. Search a 2D Matrix II
##### link: https://leetcode.com/problems/search-a-2d-matrix-ii/description/
###### tags: `binary search`
#### 1. My solution: binary search
* time complexity: $O(log n)$

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        const int row = matrix.size(), col = matrix[0].size();
        int left,right;
        int mid;
        for (int i=0;i < row; i++){
            left = 0; right=col-1;
            if (matrix[i][left] <= target && matrix[i][right]>=target){
                while (right>=left){
                    mid=left+(right-left)/2;
                    if (matrix[i][mid]==target) return true;
                    else if (matrix[i][mid] > target) right=mid-1;
                    else if (matrix[i][mid]< target) left = mid+1;
                }
            }
        }
        return false ;
    }
};

#### 2. Faster solution
* time complexity: $O(mn)$
> source : https://leetcode.com/problems/search-a-2d-matrix-ii/solutions/66140/my-concise-o-m-n-java-solution/?orderBy=hot

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0, col = matrix[0].size()-1;
        while (row< matrix.size() && col >= 0){
            if (matrix[row][col]== target) return true;
            else if (matrix[row][col] < target){
                row++;
            }
            else if (matrix[row][col] > target){
                col--;
            }
        }
        return false;
    }
};