বাইনারি সার্চ একটি দ্রুত সার্চ অ্যালগরিদম যার রান-টাইম জটিলতা O(log n)। এই অ্যালগরিদম ডিভাইড এন্ড কংকর (divide and conquer) সিদ্ধান্তে কাজ করে। এই অ্যালগরিদম সঠিকভাবে কাজ করার জন্য ডেটা সংগ্রহ সর্ট করা থাকতে হবে।
বাইনারি সার্চ কালেকশনের মাঝপথের আইটেমের সাথে তুলনা করে নির্দিষ্ট আইটেম খুঁজে বের করে। ম্যাচ হলে আইটেমের ইনডেক্স ফেরত দেয়। মাঝপথের আইটেম বড় হলে বাম সাবঅ্যারেতে, ছোট হলে ডান সাবঅ্যারেতে সার্চ করা হয়। সাবঅ্যারের আকার শূন্য হওয়া পর্যন্ত এই প্রক্রিয়া চলতে থাকে।
এটি বাইনারি সার্চ পদ্ধতিতে সর্বোচ্চ সাবঅ্যারে যোগফল বের করার প্রোগ্রাম।
অ্যালগরিদম
শুরু
maximum() ইন্টিজার ফাংশন ডিক্লেয়ার করুন (দুই ইন্টিজারের মধ্যে সর্বোচ্চ বের করতে)
val1, val2 ইন্টিজার টাইপে ডিক্লেয়ার করুন
প্যারামিটার হিসেবে পাস করুন
val1 এবং val2-এর মধ্যে সর্বোচ্চ চেক করুন
সর্বোচ্চ মান ফেরত দিন
শেষ
শুরু
MCS() ইন্টিজার ফাংশন ডিক্লেয়ার করুন (সাবঅ্যারের মাঝপথ অন্তর্ভুক্ত করে সর্বোচ্চ যোগফল বের করতে)
array[] অ্যারে এবং l, m, h ভেরিয়েবল ইন্টিজার টাইপে ডিক্লেয়ার করুন
প্যারামিটার হিসেবে পাস করুন
s, sum_of_left_part ইন্টিজার টাইপে ডিক্লেয়ার করুন
s = 0 ইনিশিয়ালাইজ করুন
sum_of_left_part = -1 ইনিশিয়ালাইজ করুন
for (int i = m; i >= l; i--)
s = s + array[i]
যদি (s > sum_of_left_part) হয়, তবে
sum_of_left_part = s
s = 0
sum_of_right_part ইন্টিজার টাইপে ডিক্লেয়ার করুন
sum_of_right_part = -1 ইনিশিয়ালাইজ করুন
for (int i = m+1; i <= h; i++)
s = s + array[i]
যদি (s > sum_of_right_part) হয়, তবে
sum_of_right_part = s
return sum_of_left_part + sum_of_right_part
শেষ
শুরু
MaximumSum_of_SubArray() ইন্টিজার ফাংশন ডিক্লেয়ার করুন
array[] অ্যারে এবং l, h ভেরিয়েবল ইন্টিজার টাইপে ডিক্লেয়ার করুন
প্যারামিটার হিসেবে পাস করুন
m ইন্টিজার টাইপে ডিক্লেয়ার করুন
যদি (l == h) হয়, তবে
return array[l]
m = (l + h) / 2
return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h))
number_of_elements এবং i ইন্টিজার টাইপে ডিক্লেয়ার করুন
"Enter the number of elements of array: " প্রিন্ট করুন
number_of_elements-এর মান ইনপুট নিন
a[number_of_elements] অ্যারে ইন্টিজার টাইপে ডিক্লেয়ার করুন
for(i = 0; i < n; i++)
"Enter the element of" প্রিন্ট করুন
অ্যারের ডেটা এলিমেন্ট ইনপুট নিন
"Maximum sum of Sub-Array is: " প্রিন্ট করুন
MaximumSum_of_SubArray(a, 0, n-1) এর ফলাফল প্রিন্ট করুন
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int maximum(int val1, int val2) { // দুটি ইন্টিজারের মধ্যে সর্বোচ্চ
return (val1 > val2) ? val1 : val2;
}
int MCS(int array[], int l, int m, int h) { // সাবঅ্যারের মাঝপথ অন্তর্ভুক্ত করে সর্বোচ্চ যোগফল
int s = 0;
int sum_of_left_part = -1;
for (int i = m; i >= l; i--) {
s = s + array[i];
if (s > sum_of_left_part)
sum_of_left_part = s;
}
s = 0;
int sum_of_right_part = -1;
for (int i = m+1; i <= h; i++) {
s = s + array[i];
if (s > sum_of_right_part)
sum_of_right_part = s;
}
return sum_of_left_part + sum_of_right_part; // মাঝপথের বাম ও ডানপাশের উপাদানগুলোর যোগফল ফেরত দিন
}
int MaximumSum_of_SubArray(int array[], int l, int h) {
int m;
if (l == h)
return array[l];
m = (l + h) / 2;
return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}
int main() {
int number_of_elements, i;
cout << "Enter the number of elements of array: ";
cin >> number_of_elements;
cout << endl;
int a[number_of_elements];
for (i = 0; i < number_of_elements; i++) {
cout << "Enter the element of " << i+1 << ": ";
cin >> a[i];
}
cout << "\nMaximum sum of Sub-Array is: " << MaximumSum_of_SubArray(a, 0, number_of_elements - 1);
return 0;
}
আউটপুট
Enter the number of elements of array: 5 Enter the element of 1: 12 Enter the element of 2: 45 Enter the element of 3: 56 Enter the element of 4: 48 Enter the element of 5: 75 Maximum sum of Sub-Array is: 236
