Count number of occurrences in a sorted array in C++: นับความถี่ใน Array เรียงแล้ว

กำหนด sorted array และตัวเลข num หาจำนวนครั้งที่ num ปรากฏใน array

ตัวอย่าง: arr = {1,1,1,2,3,4}, num = 1 → Output: 3

วิธีแก้ปัญหา

วิธีง่าย (O(n))

วนลูปนับโดยตรง

วิธีมีประสิทธิภาพ (O(log n)) - Binary Search

1. หา lower_bound (ตำแหน่งแรกที่ ≥ num)
2. หา upper_bound (ตำแหน่งแรกที่ > num)
3. ผลต่าง = จำนวนครั้ง

ตัวอย่างโค้ด C++ (Efficient)

#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);
}

Input

{1,1,1,2,3,4}, 1

Output

3