Đếm số phần tử nhỏ hơn hoặc bằng K trong mảng đã sắp xếp trong C++

Cho một mảng số nguyên. Mục tiêu là tìm số lượng phần tử của mảng nhỏ hơn hoặc bằng giá trị K cho trước.

Đầu vào

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

Đầu ra

Số phần tử nhỏ hơn hoặc bằng K: 3

Giải thích

Các số 1,2,3 nhỏ hơn hoặc bằng 12.

Đầu vào

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

Đầu ra

Số phần tử nhỏ hơn hoặc bằng K: 5

Giải thích

Các số 12, 13, 14 nhỏ hơn hoặc bằng 14.

Phương pháp đơn giản

Phương pháp sử dụng trong chương trình dưới đây

• Nhận mảng nguyên Arr[] và K.
• Hàm smallorEqual(int arr[], int k, int len) trả về số phần tử của arr[] nhỏ hơn hoặc bằng K.
• Khởi tạo biến count = 0 cho các số như vậy.
• Duyệt mảng bằng vòng lặp for. i=0 đến i<len.
• Với mỗi số arr[i], nếu <=k thì tăng count.
• Sau vòng lặp count chứa tổng số thỏa mãn điều kiện.
• Trả về count làm kết quả.

Ví dụ

#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 << "Số phần tử nhỏ hơn hoặc bằng K: " << smallorEqual(Arr, K, Length);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số phần tử nhỏ hơn hoặc bằng K: 6

Phương pháp hiệu quả (Sử dụng tìm kiếm nhị phân)

Phương pháp sử dụng trong chương trình dưới đây

• Nhận mảng nguyên Arr[] và K.
• Hàm binarySearch(int arr[], int k, int len) trả về số phần tử của arr[] nhỏ hơn hoặc bằng K.
• Chỉ số low=0, high=len-1 và mid=(low+high)/2.
• Biến index = -1.
• Dùng vòng lặp while, cho đến low <= high.
• Kiểm tra giá trị arr[mid]. Nếu <= k. Thì index=mid. low mới = mid+1.
• Ngược lại high mới = mid-1.
• Sau vòng lặp while index sẽ là chỉ số của số cuối cùng <= k.
• Trả về index+1 làm kết quả vì chỉ số mảng bắt đầu từ 0 và tất cả số từ chỉ số 0 đến index đều nhỏ hơn k.

Ví dụ

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

int binarySearch(int arr[], int k, int len) {
    int low = 0;
    int high = len - 1;
    int mid = (high + low) / 2;
    int index = -1;
    while(low <= high) {
        mid = (low + high) / 2;
        if(arr[mid] <= k) {
            index = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return (index + 1);
}

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 << "Số phần tử nhỏ hơn hoặc bằng K: " << binarySearch(Arr, K, Length);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số phần tử nhỏ hơn hoặc bằng K: 6