C++에서 2D 행렬 검색

하나의 m x n 행렬에서 값을 검색하는 효율적인 알고리즘을 작성했다고 가정합니다. 이 행렬에는 다음과 같은 몇 가지 속성이 있습니다. -

• 각 행은 왼쪽에서 오른쪽으로 정렬됩니다.
• 각 행의 첫 번째 숫자는 이전 행의 마지막 정수보다 큽니다.

따라서 행렬이 다음과 같은 경우 -

그리고 목표 값이 16이면 출력은 True가 됩니다.

단계를 살펴보겠습니다 -

• n :=행 수, n이 0이면 false 반환, m :=열 수, m =0이면 false 반환
• 낮음 :=0 및 높음 :=n – 1
• 낮은 동안 <높음
  • 중간 :=낮음 + (높음 – 낮음 + 1)/2
  • mat[mid, 0] <=target이면 low :=mid, 그렇지 않으면 high :=mid – 1
• rlow :=0 및 rhigh :=m – 1 및 ans :=0
• rlow <=rhigh
  인 동안
  • 중간 :=rlow + (rhigh - rlow)/2
  • mat[low, mid] =target이면 ans :=1이고 루프를 끊습니다.
  • 그렇지 않으면 matrix[low, mid]
  • else rhigh :=중간 – 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