কম্পিউটার টিউটোরিয়াল

সর্টেড অ্যারেতে K-এর চেয়ে ছোট বা সমান উপাদানের সংখ্যা গণনা C++-এ


একটি পূর্ণসংখ্যার অ্যারে দেওয়া আছে। লক্ষ্য হল অ্যারেতে K-এর চেয়ে ছোট বা সমান উপাদানগুলোর সংখ্যা বের করা।

সহজ পদ্ধতি

অ্যারে ট্রাভার্স করে arr[i] <= K হলে কাউন্ট বাড়ানো হয়। সর্টেড থাকায় বড় সংখ্যা পাওয়া গেলে ব্রেক করা যায়।

দক্ষ পদ্ধতি (বাইনারি সার্চ)

বাইনারি সার্চ দিয়ে K-এর চেয়ে ছোট বা সমান শেষ উপাদানের ইনডেক্স বের করা হয়। ইনডেক্স+১ হবে কাউন্ট।

উদাহরণ

ইনপুট: Arr[] = {1,2,3,14,50,69,90}, K=12

আউটপুট: K-এর চেয়ে ছোট বা সমান: ৩ (১,২,৩)

ইনপুট: Arr[] = {12,13,13,13,14,50,54,100}, K=14

আউটপুট: সংখ্যা: ৫ (১২,১৩,১৩,১৩,১৪)

C++ কোড উদাহরণ (বাইনারি সার্চ)
#include 
using namespace std;

int binarySearch(int arr[], int k, int len){
    int low = 0, high = len - 1, mid = (low + high) / 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 << "K-এর চেয়ে ছোট বা সমান সংখ্যা: " << binarySearch(Arr, K, Length);
    return 0;
}
আউটপুট

উপরোক্ত কোড রান করলে আউটপুট:

K-এর চেয়ে ছোট বা সমান সংখ্যা: ৬
  1. C++-এ সর্টেড বাইনারি অ্যারেতে ১-এর সংখ্যা গণনা (Count 1's in Sorted Binary Array)

  2. অ্যারে সব এলিমেন্ট সমান করার ন্যূনতম অপারেশন C++-তে

  3. অ্যারে সব এলিমেন্ট সমান করার ন্যূনতম অপারেশন C++-তে (ডুপ্লিকেট)

  4. C++-এ রোটেটেড সোর্টেড অ্যারেতে রোটেশন কাউন্ট বের করা