বাইনারি সার্চ কী?
বাইনারি সার্চ কেবল সর্টেড (क्रमবিন্যস্ত) লিস্ট-এ প্রয়োগযোগ্য। এই পদ্ধতিতে লিস্টকে দুটি সমান অংশে ভাগ করে মাঝপথের এলিমেন্টটি কী (key) এর সাথে তুলনা করা হয়।
তিনটি পরিস্থিতি
- মাঝপথের এলিমেন্ট কী-এর সাথে মিললে → সার্চ সফল।
- মাঝপথের এলিমেন্ট কী-এর চেয়ে বড় হলে → বাম পাশে সার্চ চালু থাকে।
- মাঝপথের এলিমেন্ট কী-এর চেয়ে ছোট হলে → ডান পাশে সার্চ চালু থাকে।
ইনপুট ও আউটপুট
- ইনপুট: সর্টেড লিস্ট, কী (key)।
- আউটপুট: সফল (key পাওয়া গেলে) অথবা অসফল।
সি প্রোগ্রাম
#include <stdio.h>
int main() {
int a[50], n, i, key, flag = 0, low, mid, high;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements (sorted): ");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter key element to search: ");
scanf("%d", &key);
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == key) {
flag = 1;
break;
} else if (a[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (flag == 1)
printf("Search is successful");
else
printf("Search is unsuccessful");
return 0;
}আউটপুট
Enter number of elements: 5 Enter elements: 23 45 57 89 90 Enter key element: 45 Search is successful
টাইম কমপ্লেক্সিটি
বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n), যা লিনিয়ার সার্চ (O(n)) এর চেয়ে অনেক দ্রুত।
