এই সমস্যায় আমাদেরকে অসীম সাজানো সংখ্যার সমন্বয়ে একটি অ্যারে দেওয়া হয়েছে৷ আমাদের কাজ হল অসীম সংখ্যার সাজানো অ্যারেতে একটি উপাদানের অবস্থান খুঁজে বের করা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9 আউটপুট
4
ব্যাখ্যা
সমাধান পদ্ধতি
একটি সাজানো অ্যারে থেকে দক্ষতার সাথে উপাদান অনুসন্ধানের জন্য, আমরা বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব। এখানে, একক শেষ বিন্দু জানা নেই, আমরা অ্যালগরিদম কিছুটা সংশোধন করব।
আমরা স্টার্ট পয়েন্টারটিকে প্রথম অবস্থানে ঠিক করব, তারপর শেষ পয়েন্টারটিকে দ্বিতীয় অবস্থানে নিয়ে যাব। এর পরে, আমরা শেষ পয়েন্টারে মানটি পরীক্ষা করব এবং মান কী থেকে কম হলে এটি দ্বিগুণ করে বৃদ্ধি করব এবং শেষ পয়েন্টারের শেষ অবস্থানের সাথে স্টার্টপয়েন্টার আপডেট করব।
যখন শেষ অবস্থানের মানটি প্রাপ্ত উপাদানের চেয়ে বেশি হয়, তখন আমরা বাইনারি অনুসন্ধান ব্যবহার করে এই সাবয়ারেতে অনুসন্ধান করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
