นับจำนวนในอาร์เรย์ที่เรียงแล้ว น้อยกว่าหรือเท่ากับ K ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์จำนวนเต็มที่เรียงแล้ว และค่า K ต้องการนับจำนวนสมาชิกที่ ≤ K

ตัวอย่าง

Input: Arr[] = {1, 2, 3, 14, 50, 69, 90}, K = 12

Output: 3

คำอธิบาย: 1, 2, 3 ≤ 12

Input: Arr[] = {12, 13, 13, 13, 14, 50, 54, 100}, K = 14

Output: 5

คำอธิบาย: 12, 13, 13, 13, 14 ≤ 14

แนวทาง Naive (Linear Scan)

1. วนลูปจากหน้าไปหลัง
2. ถ้า arr[i] ≤ K เพิ่ม count, ไม่เช่นนั้น break (เพราะเรียงแล้ว)

โค้ดตัวอย่าง (Naive)

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

int smallorEqual(int arr[], int k, int len) {
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] <= k) count++;
        else break;
    }
    return count;
}

int main() {
    int Arr[] = {1,5,11,12,19,21,32,53,70,100};
    int K = 21;
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << "Numbers <= K: " << smallorEqual(Arr, K, Length);
    return 0;
}

ผลลัพธ์

Numbers smaller or equal to K: 6

แนวทางที่มีประสิทธิภาพ (Binary Search) - O(log N)

หา upper bound — ตำแหน่งแรกที่ > K

จำนวนที่ ≤ K = upper_bound index

โค้ด Binary Search

int binarySearch(int arr[], int k, int len) {
    int low = 0, high = len - 1;
    int index = -1; // ตำแหน่งสุดท้ายที่ ≤ k
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= k) {
            index = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return index + 1; // index เริ่มที่ 0
}

// หรือใช้ STL
int countLE_STL(int arr[], int k, int len) {
    return upper_bound(arr, arr + len, k) - arr;
}

ผลลัพธ์

Numbers smaller or equal to K: 6

ความซับซ้อน

ข้อควรระวัง

• อาร์เรย์ต้องเรียงแล้ว (non-decreasing)
• upper_bound คืน iterator ตัวแรกที่ > K
• lower_bound คืน iterator ตัวแรกที่ ≥ K