বাইনারি সার্চ এবং সিকোয়েনশিয়াল বা লিনিয়ার সার্চ উভয়ই কম্পিউটার প্রোগ্রামিং-এ একটি উপাদান সার্চ করতে ব্যবহৃত হয়। বাইনারি সার্চের সময় জটিলতা O(log n) এবং সিকোয়েনশিয়াল সার্চের O(n)।
অ্যালগরিদম
শুরু বাইনারি সার্চের জন্য অ্যালগরিদম: BinarySearch() ফাংশনে 'arr' ডাটা অ্যারে এবং 'n' মানগুলির সংখ্যা, শুরু এবং শেষ ইনডেক্স, ইটারেশন কাউন্ট এবং সার্চ করার উপাদান আর্গুমেন্ট হিসেবে থাকে। ইটারেশন কাউন্টার বাড়ান এবং আইটেম মানকে a[mid]-এর সাথে তুলনা করুন। যদি আইটেম < a[mid] হয় তবে প্রথম অর্ধেক বেছে নিন অন্যথায় দ্বিতীয় অর্ধেক দিয়ে এগিয়ে যান। সফল সার্চে ইটারেশন মান ফেরত দিন। শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int BinarySearch(int a[], int start, int end, int item, int iter) {
int i, mid;
cout << "\nইটারেশন " << iter + 1;
iter++;
mid = start + (end - start + 1) / 2;
if (item > a[end] || item < a[start] || mid == end) {
cout << "\nনहीं मिला";
return iter;
} else if (item == a[mid]) {
cout << "\n আইটেম " << mid << " ইনডেক্সে পাওয়া গেছে।";
return iter;
} else if (item == a[start]) {
cout << "\n আইটেম " << start << " ইনডেক্সে পাওয়া গেছে।";
return iter;
} else if (item == a[end]) {
cout << "\n আইটেম " << end << " ইনডেক্সে পাওয়া গেছে।";
return iter;
} else if (item > a[mid])
BinarySearch(a, mid, 9, item, iter);
else
BinarySearch(a, start, mid, item, iter);
}
int LinearSearch(int a[], int n, int item) {
int i;
for (i = 0; i < n; i++) {
cout << "\nইটারেশন " << i + 1;
if (a[i] == item) {
cout << "\n আইটেম " << i << " ইনডেক্সে পাওয়া গেছে।";
return i + 1;
}
}
cout << "\nनहीं मिला";
}
int main() {
int n, i, B, L, a[10] = {2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
cout << "\nসার্চ করার উপাদান লিখুন: ";
cin >> n;
cout << "\n\n\t\t\tবাইনারি সার্চ :";
B = BinarySearch(a, 0, 9, n, 0);
cout << "\n\n\t\t\tলিনিয়ার সার্চ :";
L = LinearSearch(a, 10, n);
if (L > B)
cout << "\n\nবাইনারি সার্চ এই সার্চের জন্য ভাল।";
else if (L < B)
cout << "\n\nলিনিয়ার সার্চ এই সার্চের জন্য ভাল।";
else
cout << "\n\nউভয়ই এই সার্চের জন্য সমান দক্ষ।";
return 0;
}
আউটপুট
সার্চ করার উপাদান লিখুন: 7 বাইনারি সার্চ : ইটারেশন 1 ইটারেশন 2 ইটারেশন 3 ইটারেশন 4 আইটেম 1 ইনডেক্সে পাওয়া গেছে। লিনিয়ার সার্চ : ইটারেশন 1 ইটারেশন 2 আইটেম 1 ইনডেক্সে পাওয়া গেছে। লিনিয়ার সার্চ এই সার্চের জন্য ভাল। সার্চ করার উপাদান লিখুন: 53 বাইনারি সার্চ : ইটারেশন 1 আইটেম 9 ইনডেক্সে পাওয়া গেছে। লিনিয়ার সার্চ : ইটারেশন 1 ইটারেশন 2 ইটারেশন 3 ইটারেশন 4 ইটারেশন 5 ইটারেশন 6 ইটারেশন 7 ইটারেশন 8 ইটারেশন 9 ইটারেশন 10 আইটেম 9 ইনডেক্সে পাওয়া গেছে। বাইনারি সার্চ এই সার্চের জন্য ভাল। সার্চ করার উপাদান লিখুন: 1 বাইনারি সার্চ : ইটারেশন 1 नहीं मिला লিনিয়ার সার্চ : ইটারেশন 1 ইটারেশন 2 ইটারেশন 3 ইটারেশন 4 ইটারেশন 5 ইটারেশন 6 ইটারেশন 7 ইটারেশন 8 ইটারেশন 9 ইটারেশন 10 नहीं मिला বাইনারি সার্চ এই সার্চের জন্য ভাল।
