分治法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

Search a 2D Matrix II

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

思路: 每一行, 都是从大到小, 每一列也是从大到小. 要寻找某个元素, 那么我们可以将行和列独立开来, 从最后一列, 第一行开始寻找, 这样对目标元素形成一个包围圈. 当固定最后一列, 行元素小于target的时候, 那么自然, 这一行都小于target, 我们把row++, 此时, 当列元素大于目标的时候, 那么我们可以肯定, 目标就在这一行上, 我们对列--, 最终可以求出答案

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].empty())
                return false;
        
        int row = 0;
        int 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;
    }
};