বাইনারি অনুসন্ধান অ্যালগরিদম একটি অ্যালগরিদম যা তুলনা এবং বিভক্ত প্রক্রিয়ার উপর ভিত্তি করে। বাইনারি অনুসন্ধান অ্যালগরিদম অর্ধ-ব্যবধান অনুসন্ধান, লগারিদমিক অনুসন্ধান, বা বাইনারি চপ নামেও পরিচিত . বাইনারি অনুসন্ধান অ্যালগরিদম, একটি সাজানো অ্যারেতে লক্ষ্য মানের অবস্থান অনুসন্ধান করুন। এটি লক্ষ্য মানকে অ্যারের মধ্যম উপাদানের সাথে তুলনা করে। যদি উপাদানটি লক্ষ্য উপাদানের সমান হয় তবে অ্যালগরিদমটি সূচী প্রদান করে পাওয়া উপাদানের। এবং যদি তারা সমান না হয়, সার্চিং অ্যালগরিদম সেই অ্যারের একটি অর্ধেক অংশ ব্যবহার করে, মানের তুলনার উপর ভিত্তি করে, অ্যালগরিদম প্রথম-অর্ধেক (যখন মান মাঝখানের থেকে কম হয়) এবং দ্বিতীয় অর্ধেক ব্যবহার করে ( যখন মান মধ্যম থেকে বড় হয়)। এবং পরবর্তী অ্যারের অর্ধেকের জন্য একই কাজ করে।
Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8 ব্যাখ্যা
আমাদের অ্যারের জন্য -
আমরা 55 এর তুলনা করব, অ্যারের মধ্যম উপাদানটির সাথে যা 18, যা 55 এর কম তাই আমরা অ্যারের দ্বিতীয় অর্ধেক অর্থাৎ অ্যারে {24, 45, 55, 99} ব্যবহার করব, আবার মাঝেরটি 55। এটি দিয়ে অনুসন্ধান উপাদানের মান পরীক্ষা করুন। এবং মান মিলেছে, তাহলে আমরা এই মানের সূচকটি 8 দিয়ে ফেরত দেব।
সার্চ এলিমেন্ট যদি মাঝামাঝি থেকে ছোট হয় তাহলে আমরা ফার্স্ট হাফ ব্যবহার করতাম এবং অ্যারের মাঝখানে এলিমেন্ট পাওয়া না যাওয়া পর্যন্ত চালিয়ে যেতাম।
বাইনারি অনুসন্ধান বাস্তবায়নের জন্য আমরা দুটি উপায়ে কোড লিখতে পারি। এই দুটি উপায় শুধুমাত্র যেভাবে আমরা ফাংশনকে কল করি যেটি বাইনারি অনুসন্ধান উপাদানের জন্য পরীক্ষা করে তা স্থগিত করে। তারা হল:
-
পুনরাবৃত্তি ব্যবহার করে − এর অর্থ হল ফাংশনের ভিতরে একটি লুপ ব্যবহার করা যা মধ্যম উপাদানের সমতা পরীক্ষা করে।
-
ব্যবহার করছে এই পদ্ধতিতে, ফাংশনটি বিভিন্ন মানগুলির সাথে বারবার নিজেকে কল করে।
উদাহরণ
#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
int A[] = {0,12,6,12,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
return 0;
}
int iterativeBsearch(int A[], int size, int element) {
int start = 0;
int end = size-1;
while(start<=end) {
int mid = (start+end)/2;
if( A[mid] == element) {
return mid;
} else if( element < A[mid] ) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
} আউটপুট
55 is found at Index 8
উদাহরণ
#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
if(start>end) return -1;
int mid = (start+end)/2;
if( A[mid] == element ) return mid;
else if( element < A[mid] )
RecursiveBsearch(A, start, mid-1, element);
else
RecursiveBsearch(A, mid+1, end, element);
}
int main() {
int A[] = {0,2,6,11,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
return 0;
} আউটপুট
55 is found at Index 8
