Tìm kiếm Ma trận 2D trong C ++

Giả sử chúng ta đã viết một thuật toán hiệu quả để tìm kiếm một giá trị trong một ma trận m x n. Ma trận này có một số thuộc tính như dưới đây -

• Mỗi hàng được sắp xếp từ trái sang phải
• Số đầu tiên của mỗi hàng lớn hơn số nguyên cuối cùng của hàng trước đó.

Vì vậy, nếu ma trận giống như -

Và nếu giá trị mục tiêu là 16, thì kết quả đầu ra sẽ là True.

Hãy để chúng tôi xem các bước -

• n:=số hàng, nếu n là 0 thì trả về false, m:=số cột, nếu m =0 thì trả về false
• thấp:=0 và cao:=n - 1
• trong khi thấp
• mid:=low + (high - low + 1) / 2
• if mat [mid, 0] <=target, then low:=mid, ngược lại high:=mid - 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]]
16

Đầu ra

1