বাইনারী অনুসন্ধান৷ একটি অনুসন্ধান অ্যালগরিদম যা একটি সাজানো অ্যারেতে একটি উপাদানের অবস্থান (লক্ষ্য মান) খুঁজে পেতে ব্যবহৃত হয়। বাইনারি অনুসন্ধান প্রয়োগ করার আগে অ্যারেটি সাজানো উচিত।
বাইনারি সার্চ এই নামেও পরিচিত, লগারিদমিক সার্চ, বাইনারি চপ, হাফ ইন্টারভাল সার্চ।
কাজ করছে
বাইনারি অনুসন্ধান অ্যালগরিদম অ্যারের মধ্যম উপাদান দ্বারা অনুসন্ধান করা উপাদানটির তুলনা করে কাজ করে এবং এই তুলনার ভিত্তিতে প্রয়োজনীয় পদ্ধতি অনুসরণ করে৷
কেস 1 − element =মাঝামাঝি, উপাদানটি সূচী ফেরত পাওয়া যায়।
কেস 2 − উপাদান> মাঝামাঝি, মধ্য+1 সূচক থেকে শুরু করে n পর্যন্ত উপ-অ্যারেতে উপাদান অনুসন্ধান করুন।
কেস 3 − উপাদান <মধ্যম, 0 সূচক থেকে মধ্য -1 পর্যন্ত উপ-অ্যারেতে উপাদান অনুসন্ধান করুন।
অ্যালগোরিদম
পরামিতি প্রাথমিক_মান , শেষ_মান
Step 1 : Find the middle element of array. using , middle = initial_value + end_value / 2 ; Step 2 : If middle = element, return ‘element found’ and index. Step 3 : if middle > element, call the function with end_value = middle - 1 . Step 4 : if middle < element, call the function with start_value = middle + 1 . Step 5 : exit.
বাইনারী সার্চ অ্যালগরিদম ফাংশনের বাস্তবায়ন কল করার জন্য বার বার ব্যবহার করে। এই কল দুই ধরনের হতে পারে -
- পুনরাবৃত্ত
- পুনরাবৃত্ত
পুনরাবৃত্ত কল কোডের একই ব্লকে একাধিকবার লুপ করছে ]
পুনরাবৃত্ত কল একই ফাংশনকে বারবার কল করছে।
ইটারেটিভ কল ব্যবহার করে বাইনারি অনুসন্ধান বাস্তবায়নের প্রোগ্রাম
উদাহরণ
#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
while (start_index <= end_index){
int middle = start_index + (end_index- start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle - 1;
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 16;
int found_index = iterativeBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
} আউটপুট
Element found at index : 4
পুনরাবৃত্ত কল ব্যবহার করে বাইনারি অনুসন্ধান বাস্তবায়নের প্রোগ্রাম
উদাহরণ
#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
if (end_index >= start_index){
int middle = start_index + (end_index - start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle-1, element);
return recursiveBinarySearch(array, middle+1, end_index, element);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
} আউটপুট
Element found at index : 3
