Tìm số phần tử lớn hơn k trong mảng đã sắp xếp bằng C++

Mô tả bài toán

Cho mảng đã sắp xếp và số k. Đếm số phần tử > k.

Ví dụ

arr = {1,2,5,7,8,9}, k=4 → Output: 4 (5,7,8,9).

Giải thuật

• Duyệt tuyến tính O(N): Tìm chỉ số đầu tiên > k, trả về n - idx.
• Tìm kiếm nhị phân O(log N): Tìm chỉ số nhỏ nhất mà arr[idx] > k (upper bound).

Mã nguồn C++ (Binary Search)

#include <iostream>
using namespace std;

int findGreaterCount(int arr[], int n, int k) {
    int s=0, e=n-1, firstGreater = n;
    while (s <= e) {
        int mid = s + (e-s)/2;
        if (arr[mid] > k) { firstGreater = mid; e = mid-1; }
        else s = mid+1;
    }
    return n - firstGreater;
}

int main() {
    int arr[] = {1,3,5,7,7,8,12,21};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 5;
    cout << "The number of elements greater than k is " << findGreaterCount(arr,n,k);
    return 0;
}

Đầu ra

The number of elements greater than k is 5