在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