題目描述：

給你一個滿足下述兩條屬性的 m x n 整數矩陣：

每行中的整數從左到右按非嚴格遞增順序排列。
每行的第一個整數大于前一行的最后一個整數。
給你一個整數 target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

輸入輸出樣例：

示例 1：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

提示：
m== matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

題解：

解題思路：

思路一（暴力破解法）：

1、將二維矩陣每個元素與target進行比較。
2、復雜度分析：
① 時間復雜度：O(mn)，其中m和n分別是矩陣的行數和列數。
② 空間復雜度：O(1)。

思路二（Z字形查找）：

1、選取劃分的區間：
① 發現右上角元素的左側是比其小的元素，下方是比其大的元素（僅看當前元素所在的行和列）。
② 發現左下角元素的上側是比其小的元素，右側是比其大的元素（僅看當前元素所在的行和列）。
③ 而左上角和右下角則不能劃分大小區間
選擇以左下角元素為基準元素，（也可選右上角元素為基準元素）
相似題目(講解更詳細)：
LeetCode 熱題 100_搜索二維矩陣 II(21_240_中等_C++)（Z 字形查找)

2、復雜度分析
① 時間復雜度：O(m+n)，其中m和n分別為矩陣行數和列數，此算法最多循環 m+n 次。
② 空間復雜度：O(1)。

思路三（一次二分查找（將二維轉換為一維））：

1、將二維數組看作是一維數組進行處理（運用“%”映射到一維）。
例：

按照一維數組空間展開為：[1,3,5,7,10,11,16,20,23,30,34,60]
一維：中間元素取11，其下標為 5
二維：中間元素取11，其下標為 [1,1]
5/3(column_size)=1（行）
5%4(column_size)=1（列）
一維和二維的對應關系為：
一維元素的下標 / 矩陣列數 = 二維元素的行下標
一維元素的下標 % 矩陣列數 = 二維元素的列下標

2、復雜度分析：
① 時間復雜度：O(logmn)，其中m和n分別是矩陣的行數和列數。
② 空間復雜度：O(1)。

代碼實現

代碼實現（思路一（暴力破解法））：

bool searchMatrix1(vector<vector<int>>& matrix, int target) {for (int row = 0; row < matrix.size(); row++){for (int col = 0; col < matrix[0].size(); col++){if(matrix[row][col]==target){return true;}}}return false;
}

代碼實現（思路二（Z字形查找））：

bool searchMatrix2(vector<vector<int>>& matrix, int target) {// 初始化row為矩陣的最后一行，col為矩陣的第一列（左下角元素）int row = matrix.size() - 1;int col = 0;// 循環直到超出矩陣邊界while (row >= 0 && col < matrix[0].size()) {// 如果當前元素等于目標值，返回trueif (matrix[row][col] == target) {return true;}// 如果當前元素大于目標值，說明目標值在當前行的上方，向上移動一行else if (matrix[row][col] > target) {--row;}// 如果當前元素小于目標值，說明目標值在當前列的右側，向右移動一列else {++col;}}// 如果沒有找到目標值，返回falsereturn false;
}

代碼實現（思路三（一次二分查找（將二維轉換為一維）））：

//方法三：一次二分查找
bool searchMatrix3(vector<vector<int>>& matrix, int target) {// 獲取二維數組的行數和列數int row_size = matrix.size(), col_size = matrix[0].size();// 初始化二分查找的左邊界和右邊界// 通過將二維矩陣轉換成一維數組來處理int left = 0, right = row_size * col_size - 1, mid;// 當左邊界不超過右邊界時，繼續進行二分查找while (left <= right) {// 計算中間索引 mid，使用位移操作 >>1 代替除以2，提高效率mid = left + ((right - left) >> 1);// 將中間索引對應到二維矩陣中的位置，mid / col_size 為行，mid % col_size 為列int x = matrix[mid / col_size][mid % col_size];// 如果目標值小于當前值，移動右邊界if (x > target) {right = mid - 1;}// 如果目標值大于當前值，移動左邊界else if (x < target) {left = mid + 1;}// 找到目標值，返回 trueelse {return true;}}// 如果未找到目標值，返回 falsereturn false;
}

以思路三為例進行調試

#include<iostream>
#include<vector>
using namespace std;class Solution {
public://方法三：一次二分查找bool searchMatrix3(vector<vector<int>>& matrix, int target) {// 獲取二維數組的行數和列數int row_size = matrix.size(), col_size = matrix[0].size();// 初始化二分查找的左邊界和右邊界// 通過將二維矩陣轉換成一維數組來處理int left = 0, right = row_size * col_size - 1, mid;// 當左邊界不超過右邊界時，繼續進行二分查找while (left <= right) {// 計算中間索引 mid，使用位移操作 >>1 代替除以2，提高效率mid = left + ((right - left) >> 1);// 將中間索引對應到二維矩陣中的位置，mid / col_size 為行，mid % col_size 為列int x = matrix[mid / col_size][mid % col_size];// 如果目標值小于當前值，移動右邊界if (x > target) {right = mid - 1;}// 如果目標值大于當前值，移動左邊界else if (x < target) {left = mid + 1;}// 找到目標值，返回 trueelse {return true;}}// 如果未找到目標值，返回 falsereturn false;}};int main(){vector<vector<int>> matrix={{1,3,5,7},{10,11,16,20},{23,30,34,60}};int target=3;Solution s;if (s.searchMatrix3(matrix,target)){cout<<"true";}else{cout<<"false";}return 0;
}

部分代碼解讀

”>>“ 與 “/” 對比 ：LeetCode 熱題 100_搜索插入位置（63_35_簡單_C++）：請點擊此鏈接查看部分代碼解讀部分

LeetCode 熱題 100_搜索二維矩陣（64_74)原題鏈接
歡迎大家和我溝通交流(????)