C++で2Dマトリックスを検索する

1つのmxn行列で値を検索するための効率的なアルゴリズムを作成したとします。この行列には、以下のようないくつかのプロパティがあります-

• 各行は左から右に並べ替えられます
• 各行の最初の数値は、前の行の最後の整数よりも大きくなっています。

したがって、行列が-

また、目標値が16の場合、出力はTrueになります。

手順を見てみましょう-

• n：=行数、nが0の場合はfalseを返し、m：=列数、m=0の場合はfalseを返します
• 低：=0および高：=n – 1
• 低い<高い
  • 中：=低+（高–低+ 1）/ 2
  • mat [mid、0] <=ターゲットの場合、low：=mid、それ以外の場合、high：=mid – 1
• rlow：=0およびrhigh：=m – 1およびans：=0
• while rlow <=rhigh
  • mid：=rlow +（rhigh-rlow）/ 2
  • mat [low、mid] =targetの場合、ans：=1であり、ループを中断します
  • それ以外の場合、matrix [low、mid]
  • else rhigh：=mid – 1
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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