मान लीजिए कि हमने एक m x n मैट्रिक्स में मान की खोज करने के लिए एक कुशल एल्गोरिदम लिखा है। इस मैट्रिक्स में नीचे की तरह कुछ गुण हैं -
- प्रत्येक पंक्ति को बाएं से दाएं क्रमबद्ध किया जाता है
- प्रत्येक पंक्ति की पहली संख्या पिछली पंक्ति के अंतिम पूर्णांक से अधिक है।
तो अगर मैट्रिक्स की तरह है -
| 1 | 3 | 5 | 7 |
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 50 |
| 53 | 62 | 78 | 98 |
और अगर टारगेट वैल्यू 16 है, तो आउटपुट ट्रू होगा।
आइए चरणों को देखें -
- n:=पंक्तियों की संख्या, यदि n 0 है, तो झूठी वापसी करें, m:=स्तंभों की संख्या, यदि m =0, तो झूठी वापसी करें
- निम्न :=0 और उच्च :=n – 1
- जबकि कम <उच्च
- मध्य :=निम्न + (उच्च - निम्न + 1)/2
- यदि चटाई[मध्य, 0] <=लक्ष्य, तो निम्न :=मध्य, अन्यथा उच्च :=मध्य - 1
- rlow :=0 और rhigh :=m – 1 and ans :=0
- जबकि rlow <=rhigh
- मध्य :=rlow + (rhigh - rlow)/2
- अगर मैट [कम, मध्य] =लक्ष्य, तो उत्तर:=1, और लूप तोड़ें
- अन्यथा जब मैट्रिक्स [निम्न, मध्य] <लक्ष्य, फिर पंक्ति:=मध्य + 1
- 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
