एक आदेशित मैट्रिक्स में कुशलतापूर्वक खोज कैसे करें?

Question

मेरे पास y मैट्रिक्स द्वारा है, जहां प्रत्येक पंक्ति और प्रत्येक कॉलम नीचे दिए अनुसार आरोही क्रम में हैं।

1 5 7 9 
4 6 10 15 
8 11 12 19 
14 16 18 21 

O(x+y) में किसी संख्या के लिए इस मैट्रिक्स को कैसे खोजें?

मुझे इस प्रश्न को एक साक्षात्कार के लिए कहा गया था, लेकिन रास्ते को समझ नहीं पाया। जानना उत्सुक है कि यह किया जा सकता है या नहीं।

Answer 1

पहली पंक्ति (शीर्ष-दाएं कोने) के अंतिम तत्व से प्रारंभ करें।
key के साथ इसकी तुलना करें। हमारे पास 3 मामले हैं:

• यदि वे बराबर हैं तो हम कर रहे हैं।

• तो key उस तत्व से अधिक होता है तो इसका मतलब है key कि वह नीचे दिए तत्व को खोज लिए कदम उस पंक्ति में मौजूद नहीं हो सकता।

• तो key उस तत्व से भी कम है तो इसका मतलब यह है key छोड़ दिया की ओर है कि पंक्ति में मौजूद हो सकता है और आगे नीचे स्तंभ में मौजूद नहीं किया जा सकता है, तो तत्व इसके बारे में छोड़ दिया करने के लिए खोज चलते हैं।

आप तक यह कर रखें तत्व को खोजने या आप आगे नहीं ले जा सकते (कुंजी मौजूद नहीं है)।

छद्म कोड:

Let R be number of rows 
Let C be number of columns 

Let i = 0 
Let j = C-1 

found = false 
while(i>=0 && i<R) && (j>=0 && j<C)) 
    if (matrix[i][j] == key) 
     found = true 
     break 
    else if(matrix[i][j] > key) 
     j-- 
    else if(matrix[i][j] < key) 
     i++ 
end-while 

Answer 2

स्प्लिट 4 submatrices में मैट्रिक्स। यदि उप-मैट्रिक्स का निचला दायां कुंजी से कम है, तो इसे छोड़ दें। यदि उप-मैट्रिक्स का ऊपरी बाएं कुंजी से बड़ा है, तो इसे छोड़ दें। शेष उप-मैट्रिक्स के लिए विभाजन प्रक्रिया दोहराएं।

[अद्यतन] कुछ छद्म कोड (और जटिलता की चर्चा) के लिए जेफरी एल व्हिटलेज का जवाब this question का उत्तर देखें।

Answer 3

// the matrix is like this, from left to right is ascending, and 
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/ 
// 1 5 7 9 
// 4 6 10 15 
// 8 11 12 19 
// 14 16 18 21 
// time complexity is O(x+y), x is the count of row, and y is the count of column 

public boolean searchMatrix2(int[][] matrix, int target) { 
    int rowCount = matrix.length; 
    if(rowCount == 0) return false; 

    int colCount = matrix[0].length; 
    if(colCount == 0) return false; 

    //first find the target row, needs O(x) 
    int targetRow = 0; 
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) { 
     targetRow++; 
    } 
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y) 
    boolean result = false; 
    for(int i = 0; i < colCount; i ++) { 
     if(matrix[targetRow][i] == target) { 
      result = true; 
      break; 
     } 
    } 
    return result; 
} 

असल में, हम द्विआधारी खोज दो बार उपयोग कर सकते हैं, द्विआधारी खोज द्वारा लक्ष्य पंक्ति खोजें पहले, तो द्विआधारी खोज के द्वारा लगातार लक्ष्य मिल जाए, तो समय जटिलता ओ (LGX) + O (lgy) है , ओ (एलजीएक्स + एलजीई) है, ओ (एक्स + वाई) बेहतर है।