ধরুন আমরা এক m x n ম্যাট্রিক্সে একটি মান অনুসন্ধান করার জন্য একটি দক্ষ অ্যালগরিদম লিখেছি। এই ম্যাট্রিক্সের নিচের মত কিছু বৈশিষ্ট্য আছে −
- প্রতিটি সারি বাম থেকে ডানে সাজানো হয়
- প্রতিটি সারির প্রথম সংখ্যাটি আগের সারির শেষ পূর্ণসংখ্যার চেয়ে বড়৷
তাই ম্যাট্রিক্স যদি −
এর মত হয়| 1 | 3 | 5 | 7 |
| 10 | 11 | 16 | ৷20 |
| 23 | 30 | 34 | 50 |
| 53 | 62 | 78 | 98 |
এবং যদি লক্ষ্য মান 16 হয়, তাহলে আউটপুট হবে True।
আসুন ধাপগুলো দেখি -
- n :=সারির সংখ্যা, যদি n 0 হয়, তাহলে মিথ্যা দিন, m :=কলামের সংখ্যা, যদি m =0 হয়, তাহলে মিথ্যা দিন
- নিম্ন :=0 এবং উচ্চ :=n – 1
- যদিও কম <উচ্চ
- মধ্য :=নিম্ন + (উচ্চ – নিম্ন + 1)/2
- যদি mat[mid, 0] <=target, তারপর low :=mid, অন্যথায় high :=mid – 1
- rlow :=0 এবং rhigh :=m – 1 এবং উত্তর :=0
- যখন rlow <=rhigh
- মধ্য :=rlow + (rhigh - rlow)/2
- যদি mat[low, mid] =টার্গেট হয়, তাহলে উত্তর :=1, এবং লুপ ভাঙুন
- অন্যথায় যখন ম্যাট্রিক্স [নিম্ন, মধ্য] <লক্ষ্য, তারপর rlow :=মধ্য + 1
- অন্য 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
