ค้นหาเมทริกซ์ 2 มิติใน C++

สมมติว่าเราได้เขียนอัลกอริทึมที่มีประสิทธิภาพเพื่อค้นหาค่าในเมทริกซ์ขนาด 1 m x n เมทริกซ์นี้มีคุณสมบัติบางอย่างเช่นด้านล่าง -

• เรียงแถวจากซ้ายไปขวา
• จำนวนแรกของแต่ละแถวมากกว่าจำนวนเต็มสุดท้ายของแถวก่อนหน้า

ดังนั้นหากเมทริกซ์เป็นเหมือน −

และหากค่าเป้าหมายคือ 16 ผลลัพธ์จะเป็น True

ให้เราดูขั้นตอน -

• n :=จำนวนแถว ถ้า n เป็น 0 ให้คืนค่าเท็จ m :=จำนวนคอลัมน์ ถ้า m =0 ให้คืนค่าเท็จ
• ต่ำ :=0 และสูง :=n – 1
• ในขณะที่ต่ำ <สูง
  • กลาง :=ต่ำ + (สูง – ต่ำ + 1)/2
  • ถ้า mat[กลาง, 0] <=เป้าหมาย แล้วต่ำ :=กลาง หรือสูง :=กลาง – 1
• rlow :=0 และ rhigh :=m – 1 and ans :=0
• ในขณะที่ rlow <=rhigh
  • กลาง :=rlow + (rhigh - rlow)/2
  • ถ้า mat[ต่ำ กลาง] =เป้าหมาย แล้วตอบ :=1 และทำลายลูป
  • มิฉะนั้นเมื่อเมทริกซ์[ต่ำ กลาง] <เป้าหมาย จากนั้น rlow :=กลาง + 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