搜索二维矩阵 II
搜索二维矩阵 II
问题描述
编写一个高效的算法来搜索 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。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
思路1
暴力法。复杂度为O(m*n)。
题解
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
};思路2
每层循环，然后在每层中用二分。最坏时间复杂度为O(n*log(m))。
题解
class Solution {
public:
bool searchMatrix(vector<vector<int>> &matrix, int target) {
int n = matrix.size();
if (n == 0) return false;
int m = matrix[0].size();
int flag;
for (int i = 0; i < n; i++) {
int left = 0;
int right = m - 1;
int mid;
flag = false;
while (left <= right) {
mid = (left + right) / 2;
if (target < matrix[i][mid]) {
right=mid-1;
} else if (target > matrix[i][mid]) {
left=mid+1;
} else{
flag=1;
break;
}
}
if(flag==1){
break;
}
}
return flag;
}
};