সি++-এ অনন্ত সর্টেড অ্যারেতে একটি উপাদানের পজিশন বের করা

এই সমস্যাতে, আমাদের অনন্ত সর্টেড সংখ্যা বিশিষ্ট একটি অ্যারে দেওয়া আছে। আমাদের কাজ হলো অনন্ত সর্টেড অ্যারেতে একটি উপাদানের পজিশন (position) বের করা।

উদাহরণ দিয়ে সমস্যা বোঝা যাক,

ইনপুট

arr[] = {2, 4, 6, 8, 9, 12, 14, 17, ...}, ele = 9

আউটপুট

4 (0-based index) / 5 (1-based index)

সমাধানের পদ্ধতি

সর্টেড অ্যারে থেকে দক্ষতার সাথে উপাদান খুঁজে বের করার জন্য আমরা বাইনারি সার্চ (binary search) পদ্ধতি ব্যবহার করব। কিন্তু যেহেতু এন্ড পয়েন্ট (end point) জানা নেই, তাই অ্যালগরিদমটি কিছুটা মডিফাই (modify) করব।

আমরা স্টার্ট পয়েন্টার (start pointer) কে প্রথম পজিশনে ফিক্স করব, তারপর এন্ড পয়েন্টার (end pointer) কে দ্বিতীয় পজিশনে নেব। এরপর এন্ড পয়েন্টারের মান চেক করব এবং যদি মান কী (key) থেকে ছোট হয়, তবে এন্ড পয়েন্টারকে ডাবল (doubling) করে বাড়াব এবং স্টার্ট পয়েন্টারকে এন্ড পয়েন্টারের শেষ পজিশনে আপডেট করব।

যখন এন্ড পজিশনের মান খুঁজতে চাওয়া উপাদানের চেয়ে বড় হয়, তবে এই সাব-অ্যারেতে (subarray) বাইনারি সার্চ করে উপাদানটি খুঁজে বের করব।

সমাধান কোড:

উদাহরণ

#include<iostream>
using namespace std;

int binarySearch(int arr[], int start, int end, int ele) {
    if (end >= start) {
        int mid = start + (end - start)/2;
        if (arr[mid] == ele)
            return mid;
        if (arr[mid] > ele)
            return binarySearch(arr, start, mid-1, ele);
        return binarySearch(arr, mid+1, end, ele);
    }
    return -1;
}

int findPos(int arr[], int value) {
    int start = 0, end = 1;
    while (arr[end] < value) {
        start = end;
        end = 2*end;
    }
    return binarySearch(arr, start, end, value);
}

int main(){
    int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
    int index = findPos(arr, 9);
    if (index == -1)
        cout<<"Element not found!";
    else
        cout<<"Element found! index = "<<index;
    return 0;
}

আউটপুট

Element found! index = 5