Đếm tần suất trong mảng đã sắp xếp trong C++

Cho mảng số nguyên đã sắp xếp và số num. Đếm số lần num xuất hiện.

Ví dụ: {1,1,1,2,3,4}, num=1 → 3.

Hai cách:

• Naive: Duyệt tuyến tính đếm.
• Hiệu quả: Dùng lower_bound và upper_bound (binary search) để tìm vị trí đầu và cuối của num, độ phức tạp O(log n).

Ví dụ (Naive)

#include <iostream>
using namespace std;

int frequency_count(int arr[], int num, int size) {
    int count = 0;
    for (int i = 0; i < size; i++)
        if (num == arr[i]) count++;
    return count;
}

int main() {
    int arr[] = {1,1,1,2,3,4};
    int num = 1;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << frequency_count(arr, num, size);
    return 0;
}

Ví dụ (Hiệu quả)

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

int frequency_count(int arr[], int num, int size) {
    int* first = lower_bound(arr, arr + size, num);
    if (first == arr + size || *first != num) return 0;
    int* last = upper_bound(first, arr + size, num);
    return last - first;
}

int main() {
    int arr[] = {1,1,1,2,3,4};
    int num = 1;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << frequency_count(arr, num, size);
    return 0;
}

Đầu ra

Count of number of occurrences (or frequency) in a sorted array are: 3