Ở đây chúng ta sẽ thấy cách tìm floor (sàn) và ceiling (trần) trong một mảng chưa sắp xếp. Giá trị floor là phần tử lớn nhất mà nhỏ hơn hoặc bằng x, và giá trị ceiling là giá trị nhỏ nhất mà lớn hơn x. Nếu mảng A = [5, 6, 8, 9, 6, 5, 5, 6], và x là 7, thì giá trị floor là 6, và giá trị ceiling là 8.
Để giải quyết bài toán này, chúng ta sẽ làm theo phương pháp tìm kiếm tuyến tính. Chúng ta sẽ duyệt mảng và theo dõi hai khoảng cách đối với x.
- Khoảng cách nhỏ nhất của phần tử lớn hơn hoặc bằng x
- Khoảng cách nhỏ nhất của phần tử nhỏ hơn hoặc bằng x
- Cuối cùng, in phần tử với khoảng cách nhỏ nhất
Ví dụ
#include<iostream> using namespace std; void floorCeilingPair(int arr[], int n, int x) { int floor_index, ceiling_index; int floor_dist = INT_MAX, ceil_dist = INT_MAX; for (int i=0; i<n; i++) { if (arr[i] >= x && ceil_dist > (arr[i] - x)) { ceiling_index = i; ceil_dist = arr[i] - x; } if (arr[i] <= x && floor_dist > (x - arr[i])) { floor_index = i; floor_dist = x - arr[i]; } } if (floor_dist == INT_MAX) cout << "Floor not found" << endl; else cout << "Floor value is " << arr[floor_index] << endl; if (ceil_dist == INT_MAX) cout << "Ceiling not found" << endl; else cout << "Ceil value is " << arr[ceiling_index] << endl; } int main() { int arr[] = {5, 6, 8, 9, 6, 5, 5, 6}; int n = sizeof(arr)/sizeof(int); int x = 7; floorCeilingPair(arr, n, x); }
Kết quả
Floor value is 6 Ceil value is 8