Truy vấn số phần tử lớn hơn / lớn hơn hoặc bằng x bằng C++ (Binary Search)

Cho mảng, hai loại truy vấn:

• Loại 0 — đếm số phần tử lớn hơn hoặc bằng x.
• Loại 1 — đếm số phần tử lớn hơn x.

Ví dụ:

Input : arr[] = { 10, 15, 30, 40, 45 }, Q = 3 Query 1: 0 50 Query 2: 1 40 Query 3: 0 30 Output : 0  1  3 Giải thích: x=50, loại 0: không có phần tử ≥50. x=40, loại 1: chỉ 45 > 40. x=30, loại 0: 30, 40, 45 ≥ 30 → 3 phần tử.

Cách vét cạn

Duyệt toàn mảng mỗi truy vấn. Độ phức tạp O(N×Q).

Ví dụ

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

void query(int *arr, int n, int type, int val) {
    int count = 0;
    if (!type) {
        for (int i = 0; i < n; i++) if (arr[i] >= val) count++;
    } else {
        for (int i = 0; i < n; i++) if (arr[i] > val) count++;
    }
    cout << count << "\n";
}

int main() {
    int ARR[] = { 10, 15, 30, 40, 45 };
    int n = sizeof(ARR)/sizeof(ARR[0]);
    query(ARR, n, 0, 50);
    query(ARR, n, 1, 40);
    query(ARR, n, 0, 30);
    return 0;
}

Kết quả

0 1 3

Cách hiệu quả: Binary Search (Tìm kiếm nhị phân)

Sắp xếp mảng. Loại 0 dùng lower_bound (phần tử đầu tiên ≥ x). Loại 1 dùng upper_bound (phần tử đầu tiên > x). Số phần tử thỏa mãn = n - index. Độ phức tạp O(N log N + Q log N).

Ví dụ

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

void lowerbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (arr[mid] >= val) r = mid;
        else l = mid;
    }
    if (r == n) cout << "0\n";
    else cout << n - r << "\n";
}

void upperbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (arr[mid] > val) r = mid;
        else l = mid;
    }
    if (r == n) cout << "0\n";
    else cout << n - r << "\n";
}

void query(int *arr, int n, int type, int val) {
    if (!type) lowerbound(arr, n, val);
    else upperbound(arr, n, val);
}

int main() {
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr + n);
    query(arr, n, 0, 5);
    query(arr, n, 1, 3);
    query(arr, n, 0, 3);
    return 0;
}

Kết quả

0 1 2

Giải thích

Sắp xếp mảng → binary search tìm vị trí ranh giới. Phần tử sau vị trí đó đều thỏa điều kiện. Trả về n - pos.

Kết luận

Giải quyết truy vấn đếm phần tử > x hoặc ≥ x bằng Binary Search sau khi sort. Code C++ mẫu, độ phức tạp O(N log N + Q log N).