在C ++中搜索2D矩阵
假设我们编写了一种有效的算法来搜索一个mxn矩阵中的值。该矩阵具有以下一些属性-
每行从左到右排序
每行的第一个数字大于前一行的最后一个整数。
所以如果矩阵像-
如果目标值为16，则输出为True。
让我们看看步骤-
n：=行数，如果n为0，则返回false，m：=列数，如果m=0，则返回false
低：=0和高：=n–1
从低到高
中：=低+（高–低+1）/2
如果mat[mid，0]<=目标，则低：=中，否则高：=中–1
rlow：=0和rhigh：=m–1和ans：=0
而rlow<=rhigh
中：=rlow+(rhigh-rlow)/2
如果mat[low，mid]=目标，则ans：=1，并中断循环
否则，当matrix[low，mid]<目标，然后rlow：=mid+1
其他rhigh：=中–1
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
lli n,m;
n = matrix.size();
if(!n)return false;
m = matrix[0].size();
if(!m)return false;
lli low = 0, high = n-1;
while(low<high){
lli mid = low + ( high - low +1)/2;
if(matrix[mid][0]<=target)low = mid;
else high = mid -1;
}
lli rlow = 0, rhigh = m-1;
lli ans = 0;
while(rlow<=rhigh){
lli mid = rlow+(rhigh - rlow)/2;
if(matrix[low][mid] == target){
ans =1;
break;
}else if(matrix[low][mid]<target)rlow=mid+1;
else rhigh= mid-1;
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,3,5,7},{10,11,16,20},{23,30,34,50},{53,62,78,98}};
cout << ob.searchMatrix(v, 16);
}输入项
[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]] 16
输出结果
1