在C ++中搜索2D矩阵

假设我们编写了一种有效的算法来搜索一个mxn矩阵中的值。该矩阵具有以下一些属性-

  • 每行从左到右排序

  • 每行的第一个数字大于前一行的最后一个整数。

所以如果矩阵像-

1357
10111620
23303450
53627898

如果目标值为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