Search a 2D Matrix - ค้นหาในเมทริกซ์ 2 มิติใน C++

ภาพรวมปัญหา

ค้นหาค่า target ในเมทริกซ์ m×n ที่มีคุณสมบัติ:

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

ตัวอย่าง

Target = 16 → True

อัลกอริทึม (Binary Search 2 ชั้น)

1. Binary Search หาแถวที่ target อาจอยู่ (เปรียบเทียบกับคอลัมน์แรก)
2. Binary Search ในแถวนั้นหา target

ตัวอย่างโค้ด C++

#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 = matrix.size();
        if(!n) return false;
        lli 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, 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);
}

Input / Output

Input:  [[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]] 16
Output: 1