Tìm Floor và Ceil của mảng đã sắp xếp bằng C++ STL

Cho mảng đã sắp xếp tăng dần, ta muốn tìm Floor (phần tử lớn nhất ≤ x) và Ceil (phần tử nhỏ nhất ≥ x) cho nhiều giá trị truy vấn. STL cung cấp lower_bound và upper_bound để giải quyết hiệu quả O(log n) mỗi truy vấn.

Định nghĩa

• Floor(x): Phần tử lớn nhất trong mảng mà ≤ x. Nếu x nhỏ hơn tất cả → không tồn tại.
• Ceil(x): Phần tử nhỏ nhất trong mảng mà ≥ x. Nếu x lớn hơn tất cả → không tồn tại.

Sử dụng STL

• lower_bound(arr, arr+n, x): Trả về iterator đến phần tử đầu tiên ≥ x.
• upper_bound(arr, arr+n, x): Trả về iterator đến phần tử đầu tiên > x.

Logic Floor

auto it = lower_bound(arr, arr+n, x);
if (it == arr+n) floor = arr[n-1];           // x lớn hơn tất cả
else if (*it == x) floor = *it;              // x có trong mảng
else if (it == arr) floor = KHÔNG TỒN TẠI;   // x nhỏ hơn tất cả
else floor = *(it-1);                        // phần tử ngay trước it

Logic Ceil

auto it = lower_bound(arr, arr+n, x); // lower_bound cũng cho ceil
if (it == arr+n) ceil = KHÔNG TỒN TẠI;
else ceil = *it;

Ví dụ code C++ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

void printFloor(int arr[], int n, int query[], int q) {
    cout << "Floor: ";
    for (int i = 0; i < q; i++) {
        auto it = lower_bound(arr, arr+n, query[i]);
        if (it == arr+n) cout << arr[n-1] << " ";
        else if (it == arr && *it > query[i]) cout << "NA ";
        else if (*it == query[i]) cout << *it << " ";
        else cout << *(it-1) << " ";
    }
    cout << endl;
}

void printCeil(int arr[], int n, int query[], int q) {
    cout << "Ceil:  ";
    for (int i = 0; i < q; i++) {
        auto it = lower_bound(arr, arr+n, query[i]);
        if (it == arr+n) cout << "NA ";
        else cout << *it << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 4, 7, 11, 12, 23, 30, 32};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int query[] = {1, 3, 5, 7, 20, 24};
    int q = sizeof(query)/sizeof(query[0]);
    
    cout << "Mảng: ";
    for (int x : arr) cout << x << " ";
    cout << "\nTruy vấn: ";
    for (int x : query) cout << x << " ";
    cout << "\n\n";
    
    printFloor(arr, n, query, q);
    printCeil(arr, n, query, q);
    return 0;
}

Đầu ra

Mảng: 1 2 4 7 11 12 23 30 32
Truy vấn: 1 3 5 7 20 24

Floor: 1 2 4 7 12 23
Ceil:  1 4 7 7 23 30

Phân tích độ phức tạp

• Thời gian: O(q log n) cho q truy vấn.
• Không gian: O(1) thêm.