বাইনারি সার্চ (Binary Search) হল একটি সার্চ অ্যালগরিদম যা একটি সোর্টেড (sorted) অ্যারেতে একটি এলিমেন্ট (টার্গেট ভ্যালু) এর পজিশন খুঁজে বের করতে ব্যবহৃত হয়। বাইনারি সার্চ প্রয়োগ করার আগে অ্যারেটি সোর্ট করা থাকতে হবে।
বাইনারি সার্চকে আরো নামে ডাকা হয়: লগারিদমিক সার্চ (logarithmic search), বাইনারি চপ (binary chop), হাফ ইন্টারভাল সার্চ (half interval search)।
কাজ করার পদ্ধতি (Working)
বাইনারি সার্চ অ্যালগরিদমটি মাঝপথের এলিমেন্ট (middle element) দিয়ে সার্চ করার এলিমেন্টটি তুলনা করে এবং এই তুলনার ফলাফলের উপর ভিত্তি করে পরবর্তী ধাপ নেয়।
- Case 1 − এলিমেন্ট = মাঝপথ, এলিমেন্টটি পাওয়া গেলে ইন্ডেক্স রিটার্ন করা।
- Case 2 − এলিমেন্ট > মাঝপথ, মাঝপথ+1 ইন্ডেক্স থেকে n পর্যন্ত সাব-অ্যারেতে সার্চ করা।
- Case 3 − এলিমেন্ট < মাঝপথ, ০ ইন্ডেক্স থেকে মাঝপথ-১ পর্যন্ত সাব-অ্যারেতে সার্চ করা।
আলগরিদম (Algorithm)
প্যারামিটার: initial_value, end_value
Step 1: অ্যারেতে মাঝপথের এলিমেন্ট বের করা। middle = initial_value + end_value / 2 Step 2: যদি middle = element হয়, তবে 'element found' এবং ইন্ডেক্স রিটার্ন করা। Step 3: যদি middle > element হয়, তবে ফাংশনকে end_value = middle - 1 দিয়ে কল করা। Step 4: যদি middle < element হয়, তবে ফাংশনকে start_value = middle + 1 দিয়ে কল করা। Step 5: এক্সিট (Exit)।
বাইনারি সার্চ অ্যালগরিদম ফাংশন ইমপ্লিমেন্টেশন ফাংশনকে বারবার কল করে। এই কল দুভাবে হতে পারে:
- ইটেরেটিভ (Iterative) − একই ব্লক কোড বারবার লুপ করে চালানো।
- রিকার্সিভ (Recursive) − একই ফাংশনকে বারবার কল করা।
ইটেরেটিভ কল ব্যবহার করে বাইনারি সার্চ ইমপ্লিমেন্টেশন
উদাহরণ (C প্রোগ্রাম)
#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
রিকার্সিভ কল ব্যবহার করে বাইনারি সার্চ ইমপ্লিমেন্টেশন
উদাহরণ (C প্রোগ্রাম)
#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
ব্যাখ্যা: বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n)। ইটেরেটিভ ভার্সন স্ট্যাক স্পেস বাঁচায়, রিকার্সিভ ভার্সন কোড ক্লিনার (cleaner) কিন্তু স্ট্যাক স্পেস নেয়। সর্টেড অ্যারে থাকা বাধ্যতামূলক।
