C++ में 2D मैट्रिक्स में खोज (Search a 2D Matrix)

मान लीजिए हमें एक कुशल एल्गोरिदम लिखना है जो m x n मैट्रिक्स में एक मान खोजता है। इस मैट्रिक्स के कुछ गुण हैं:

प्रत्येक पंक्ति बाएं से दाएं क्रमबद्ध है
प्रत्येक पंक्ति का पहला नंबर पिछली पंक्ति के अंतिम पूर्णांक से बड़ा है।

यदि मैट्रिक्स इस तरह है:

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

और यदि लक्ष्य मान 16 है, तो आउटपुट True होगा।

आइए चरण देखें:

n := पंक्तियों की संख्या, यदि n 0 है, तो false वापस करें, m := कॉलम की संख्या, यदि m = 0, तो false वापस करें
low := 0 और high := n – 1
जब तक low < high:
- mid := low + (high – low + 1)/2
- यदि mat[mid, 0] <= target, तो low := mid, अन्यथा high := mid – 1
rlow := 0 और rhigh := m – 1 और ans := 0
जब तक rlow <= rhigh:
- mid := rlow + (rhigh - rlow)/2
- यदि mat[low, mid] = target, तो ans := 1, और लूप तोड़ें
- अन्यथा जब matrix[low, mid] < target, तो rlow := mid + 1
- अन्यथा rhigh := mid – 1
ans वापस करें

उदाहरण

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

int 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