问题：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：    每行的元素从左到右升序排列。    每列的元素从上到下升序排列。示例:现有矩阵 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 = 5，返回 true。给定 target = 20，返回 false。

GitHub实现：

思路：二分查找，分治法

参考：

一、二分查找

遍历矩阵中的每一行

对于第i行，初始left和right分别是数组的第一个和最后一个元素的下标，middle=（left+right）/2。

    如果matrix[i][middle] = target，则找到

    如果matrix[i][middle] < target，说明target不可能存在于数组的左半边，left = middle + 1

    如果matrix[i][middle] > target，说明target不可能存在于数组的右半边，right = middle - 1

完成遍历后都没有找到，则说明矩阵中没有要寻找的目标

//二分查找         public bool SearchMatrix(int[,] matrix, int target)        {            if (matrix.Length == 0) return false;            //行            var m = matrix.GetLength(0);            //列            var n = matrix.GetLength(1);            for (int i = 0; i < m; i++)            {                var left = 0;                var right = n - 1;                while (left <= right)                {                    var middle = (left + right) / 2;                    if (matrix[i, middle] == target) return true;                    if (matrix[i, middle] < target) left = middle + 1;                    else right = middle - 1;                }            }            return false;        }

二、分治法

右上角的元素是这一行中最大的元素，同时又是这一列中最小的元素。比较右上角元素和目标：

    若右上角元素等于目标，则找到

    若右上角元素大于目标，则目标不可能存在于当前矩阵的最后一列，问题规模可以减小为在去掉最后一列的子矩阵中寻找目标

    若右上角元素小于目标，则目标不可能存在于当前矩阵的第一行，问题规模可以减小为在去掉第一行的子矩阵中寻找目标

若最后矩阵减小为空，则说明不存在

//分治法         public bool SearchMatrix2(int[,] matrix, int target)        {            if (matrix.Length == 0) return false;            //行            var m = matrix.GetLength(0);            //列            var n = matrix.GetLength(1);            var i = 0;            var j = n - 1;            while (j >= 0 && i < m)            {                if (matrix[i, j] == target) return true;                if (matrix[i, j] > target) j--;                else i++;            }            return false;        }