Đếm các phần tử nhỏ hơn hoặc bằng nhau trong mảng được sắp xếp trong C ++

Chúng tôi được cung cấp một mảng các số nguyên. Mục đích là để tìm số phần tử của một mảng nhỏ hơn hoặc bằng giá trị K.

Đầu vào

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

Đầu ra

Numbers smaller or equal to K: 3

Giải thích

Numbers 1,2,3 is smaller or equal to 12.

Đầu vào

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

Đầu ra

Numbers smaller or equal to K: 5

Giải thích

Numbers 12, 13, 14 are smaller or equal to 14.

Phương pháp tiếp cận ngây thơ

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng ta lấy mảng số nguyên Arr [] và K.

• Hàm smallorEqual (int arr [], int k, int len) trả về số phần tử của arr [] nhỏ hoặc bằng K

• Lấy số lượng biến ban đầu là 0 cho những số như vậy.

• Duyệt mảng số bằng vòng lặp for. i =0 đến i

• Bây giờ đối với mỗi số arr [i], nếu nó là <=k, thì số gia tăng.

• Ở cuối vòng lặp đếm sẽ có tổng số thỏa mãn điều kiện.

• Trả lại kết quả là số lượng.

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 <<"Numbers smaller or equal to K: "<<smallorEqual(Arr,K,Length);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Numbers smaller or equal to K: 6

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng ta lấy mảng số nguyên Arr [] và K.

• Hàm binarySearch (int arr [], int k, int len) trả về số phần tử của arr [] nhỏ hoặc bằng K

• Lấy các chỉ số low =0, high =len-1 và mid =(low + high) / 2; / p>

• Lấy chỉ số biến =-1;

• Sử dụng vòng lặp while, đến mức thấp <=high

• Kiểm tra giá trị của arr [mid]. Nếu nó là <=k. Sau đó, chỉ số =giữa. Thấp mới =trung bình + 1

• Nếu không thì mới high =mid-1.

• Ở cuối vòng lặp while, chỉ mục sẽ chỉ mục của số cuối cùng <=k.

• Kết quả là trả về chỉ mục + 1 vì lập chỉ mục mảng bắt đầu từ 0 và tất cả các số từ chỉ mục 0 đến chỉ mục đề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 <<"Numbers smaller or equal to K: "<<binarySearch(Arr,K,Length);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Numbers smaller or equal to K: 6