Giả sử chúng ta viết một thuật toán hiệu quả để tìm một giá trị trong ma trận m x n. Ma trận có các tính chất:
- Mỗi hàng được sắp xếp từ trái sang phải
- Số đầu tiên của mỗi hàng lớn hơn số cuối cùng của hàng trước.
Ví dụ ma trận:
| 1 | 3 | 5 | 7 |
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 50 |
| 53 | 62 | 78 | 98 |
Nếu target = 16, kết quả là True.
Các bước thực hiện:
- n := số hàng, nếu n = 0 return false, m := số cột, nếu m = 0 return false
- low := 0 và high := n – 1
- while low < high
- mid := low + (high – low + 1)/2
- nếu mat[mid, 0] <= target, low := mid, ngược lại high := mid – 1
- rlow := 0 và rhigh := m – 1 và ans := 0
- while rlow <= rhigh
- mid := rlow + (rhigh - rlow)/2
- nếu mat[low, mid] = target, ans := 1, break
- ngược lại nếu matrix[low, mid] < target, rlow := mid + 1
- ngược lại rhigh := mid – 1
- return ans
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#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); }Input
[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]] 16
Output
1