在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