# 【LeetCode】 74. Search a 2D Matrix

## Description
> 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.

> 寫一個有效的演算法，在m*n的矩陣中搜尋一個數字。
> - 矩陣中的數字每一個row由左到右已經排序過。
> - 每一個row的第一個數字一定比上一個row最後一個數字還要大。

## Example:

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true


Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

## Solution

* 先以每一個row的第一個數字去找目標應該在哪一個row之中。
* 找到row之後，再以linear search去搜尋。

### Code

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

###### tags: `LeetCode` `C++`