编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]target = 3输出: true
示例 2:
输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]target = 13输出: false
1 #include "_000库函数.h" 2 3 4 //题目要求使用高效算法，但不知最高效的是哪个 5 //本解法复杂度为m+n 6 class Solution { 7 public: 8 bool searchMatrix(vector >& matrix, int target) { 9 if (matrix.empty() || matrix[0].empty())return false;10 int m = matrix.size();11 int n = matrix[0].size();12 if (target< matrix[0][0] || target>matrix[m - 1][n - 1])return false;13 for (int i = 0; i < m; ++i)14 if (target >= matrix[i][0] && target <= matrix[i][n - 1]) {15 for (int j = 0; j < n; ++j)16 if (target == matrix[i][j])return true;17 return false;18 }19 return false;20 }21 };22 23 //当然这道题也可以使用一次二分查找法，如果我们按S型遍历该二维数组，24 //可以得到一个有序的一维数组，那么我们只需要用一次二分查找法，25 //而关键就在于坐标的转换，如何把二维坐标和一维坐标转换是关键点，26 //把一个长度为n的一维数组转化为m*n的二维数组(m*n = n)后，27 //那么原一维数组中下标为i的元素将出现在二维数组中的[i / n][i%n]的位置，28 //29 30 // One binary search31 class Solution {32 public:33 bool searchMatrix(vector > &matrix, int target) {34 if (matrix.empty() || matrix[0].empty()) return false;35 if (target < matrix[0][0] || target > matrix.back().back()) return false;36 int m = matrix.size(), n = matrix[0].size();37 int left = 0, right = m * n - 1;38 while (left <= right) {39 int mid = (left + right) / 2;40 if (matrix[mid / n][mid % n] == target) return true;41 else if (matrix[mid / n][mid % n] < target) left = mid + 1;42 else right = mid - 1;43 }44 return false;45 }46 };47 48 void T074() {49 Solution s;50 vector >v;51 v = { { 1,3,5,7},{ 10,11,16,20},{ 23,30,34,50} };52 cout << s.searchMatrix(v, 3) << endl;53 cout << s.searchMatrix(v, 13) << endl;54 55 56 }