একটা অ্যারের এলিমেন্টগুলোর মধ্য থেকে কোন একটা নির্দিষ্ট এলিমেন্ট খোঁজার সহজ এবং দ্রুততম পদ্ধতি হল বাইনারী সার্চ। লিনিয়ার সার্চ অ্যালগরিদম থেকে বাইনারী সার্চ অ্যালগরিদম দ্রুত হবার প্রধান কারন হল এটা অ্যারের শুধুমাত্র অর্ধেক এলিমেন্ট চেক করে। আজকে আমরা বাইনারী সার্চ অ্যালগরিদম কিভাবে কাজ করে তা শিখব এবং সেই সাথে বাইনারী সার্চ অ্যালগরিদমের সি, সি++, এবং জাভা ইম্লিমেন্টেশন দেখব।
বাইনারী সার্চ অ্যালগরিদমের সুবিধাঃ
১। বাইনারী সার্চ অ্যালগরিদম অ্যারের অর্ধেক অংশ নিয়ে কাজ করে।
২। অ্যারের এলিমেন্ট সংখ্যা বেশী হলেও এটি ব্যবহার করা যায়।
৩। লিনিয়ার সার্চ থেকে এটি অনেক দ্রুত।
বাইনারী সার্চ অ্যালগরিদমের অসুবিধাঃ
১। অ্যারের এলিমেন্টগুলো সর্ট করতে হয়।
অ্যালগরিদম কমপ্লেক্সিটিঃ
Worst Case: O(log n)
Average Case: O(log n)
বাইনারী সার্চ অ্যালগরিদম কিভাবে কাজ করে?
বাইনারী সার্চ অ্যালগরিদম শুরুতে অ্যারের এলিমেন্টগুলোর মধ্যম পজিশনের ভ্যালু বের করে। যেম্ন, অ্যারেতে n সংখ্যক এলিমেন্ট থাকলে মধ্যম মান হবে (n-1/2) তম এলিমেন্ট হবে ঐই অ্যারের মধ্যম মান। ধরুন, অ্যারের মধ্যম মানে k ভ্যালুর এলিমেন্টটা আছে। এখন ১ম ধাপে k এর সাথে আমরা যে এলিমেন্ট সার্চ করছি তা মিলে কিনা দেখবে। যদি মিলে যায় তাহলে মধ্যম মানটার পজিশন হবে আমাদের সার্চিং এলিমেন্টের পজিশন, মানে (n-1/2)। যেহেতু আমরা সার্চ এলিমেন্টের পজিশন পেয়ে গেছি তাই আমাদেরকে অ্যারের আর কোন অংশ নিয়ে কাজ করতে হবে না। যদি k এর সাথে আমাদের সার্চ এলিমেন্ট না মিলে তখন আমাদের সামনে দুইটা অপশন আসবেঃ
১। সার্চিং এলিমেন্টটা কি k থেকে বড় ?
২। নাকি k থেকে ছোট? [এখানে k = অ্যারের মধ্যম পজিশনে যে এলিমেন্ট আছে]
যদি ছোট হয় তাহলে আমাদেরকে অ্যারের মধ্যম পজিশনের এক ঘর আগে থেকে শুরু করে ১ম পর্যন্ত চেক করতে হবে এবং প্রতিবার চেক করার পর আমাদের সার্চিং এলিমেন্টটা না পেলে মধ্যম পজিশনের মান 1 করে কমাতে হবে।
আর যদি বড় হয় তাহলে আমাদেরকে মধ্যম পজিশনের এক ঘর পরে থেকে শুরু করে অ্যারের শেষ এলিমেন্ট পর্যন্ত চেক করতে হবে এবং প্রতিবার চেক করার পর আমাদের সার্চিং এলিমেন্টটা না পেলে মধ্যম পজিশনের মান 1 করে বাড়াতে হবে।
একটা উদাহরন দিয়ে ব্যাখ্যা করলে ব্যাপারটা আপনাদের বুঝতে আরো সুবিধা হবে। ধরুন, arr নামে আমাদের একটা অ্যারে আছে এবং অ্যারের এলিমেন্টগুলো হলঃ 12, 5, 67, 35, 62, 10, 44, 55, 3, 4, 1 এবং আমাদেরকে সার্চ করতে হবে 55। তাহলে অ্যারে সর্ট করলে হবেঃ 1, 3, 4, 5, 10, 12, 35, 44, 55, 62, 67 এবং মধ্যম মানের পজিশন হবে 5 [যেহেতু অ্যারের ইনডেক্স ০ থেকে শুরু হয়].
১ম ধাপঃ এক্ষেত্রে অ্যারের মধ্যম পজিশনে (arr[5]) আছে 12 এবং আমাদের সার্চিং এলিমেন্ট 55. তাহলে আমাদের সার্চিং এলিমেন্ট অ্যারের মধ্যম পজিশনে নেই।
২য় ধাপঃ এখন আমাদের দেখতে হবে সার্চিং এলিমেন্টটা অ্যারের মধ্যম মান থেকে বড় নাকি ছোট। আমাদের অ্যারের ক্ষেত্রে সার্চিং এলিমেন্ট মধ্যম মান থেকে বড় তাই আমাদেরকে অ্যারের মধ্যোম পজিশনের এক ঘর পর থেকে শুরু করে অ্যারের শেষ পর্যন্ত চেক করতে হবে। প্রতিবার চেক করার পর যদি সার্চিং এলিমেন্টটা না মিলে তাহলে মধ্যম পজিশন 1 করে বাড়াতে হবে।
২য় ধাপঃ ১ – অ্যারের মধ্যম পজিশন 5, তাহলে আমাদেরকে মধ্যম পজিশন 6 থেকে শুরু করতে হবে। arr[6] এ আছে 35 কিন্তু আমাদের সার্চিং এলিমেন্ট 55, সার্চিং এলিমেন্ট অ্যারের arr[6] পজিশনের এলিমেন্টের সাথে মিলে নাই তাই আমাদেরকে মধ্যম পজিশনের মান 1 বাড়াতে হবে। তাহলে এখন মধ্যম পজিশন হবে 7.
২য় ধাপঃ ২ – এক্ষেত্রে arr[7] এ আছে 44 কিন্তু আমাদের সার্চিং এলিমেন্ট 55, সার্চিং এলিমেন্ট অ্যারের arr[7] পজিশনের এলিমেন্টের সাথে মিলে নাই তাই আমাদেরকে মধ্যম পজিশনের মান 1 বাড়াতে হবে। তাহলে এখন মধ্যম পজিশন হবে 8.
৩য় ধাপঃ ৩ – এক্ষেত্রে arr[8] এ আছে 55 এবং আমাদের সার্চিং এলিমেন্ট 55, সার্চিং এলিমেন্টের সাথে মধ্যম মান মিলে গেছে, তাহলে আমাদের সার্চিং এলিমেন্টের পজিশন হবে 8.
লক্ষ্য করবেন, যতক্ষন পর্যন্ত আমাদের সার্চিং ভ্যালুর সাথে অ্যারের বর্তমান পজিশনের ভ্যালু মিলে নাই ততক্ষন পর্যত্ন আমি অ্যারের মধ্যম মানের পজিশন এক এক করে বৃদ্ধি করেছি। এটা করেছি নতুন কোন ভ্যারিয়েবল ডিক্লায়ার না করার জন্য। নতুন ভ্যারিয়েবল ডিক্লায়ার করলে শুরুতে তার ভ্যালু ডিক্লায়ার করতে হবে (n-1)/2. [যেখানে n = অ্যারের এলিমেন্ট সংখ্যা]।
নোটঃ এই পোষ্টটা অ্যারের এলিমেন্ট সংখ্যা বিজোড় ধরে লিখা হয়েছে। জোড় নাম্বারের ক্ষেত্রে মধ্যম মান বের করার জন্য অন্য পদ্ধতি আছে।
কোড – সিঃ
#include <stdio.h>
int main()
{
int i, j, n, mid, srch, Start, End;
printf("How many Elements?: ");
scanf("%d", &n);
int arr[n+2];
printf("Enter the elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the element to search: ");
scanf("%d", &srch);
for(i = 0; i < n; i++)
{
for(j = i + 1; j arr[j])
{
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
Start = 0; End = n-1;
mid = (Start + End)/2;
while(Start <= End && arr[mid] != srch)
{
if(srch < arr[mid])
{
End = mid-1;
}
else
{
Start = mid+1;
}
mid = (Start + End)/2;
}
if(arr[mid] == srch)
{
printf("Element found at the position: %d\n", mid);
}
else
{
printf("Element is not available on the array.\n");
}
return 0;
}
কোড – সি প্লাস প্লাস
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int i, n, mid, srch, Start, End;
cout<<"How many Elements?: ";
cin>>n;
int arr[n+2];
cout<<"Enter the elements:"<<endl;
for(i = 0; i < n; i++)
{
cin>>arr[i];
}
cout<<"Enter the element to search: ";
cin>>srch;
sort(arr, arr+n); //Sorting Array Elements
Start = 0; End = n-1;
mid = (Start + End)/2;
while(Start <= End && arr[mid] != srch)
{
if(srch < arr[mid])
{
End = mid-1;
}
else
{
Start = mid+1;
}
mid = (Start + End)/2;
}
if(arr[mid] == srch)
{
cout<<"Element found at the position: "<<mid<<endl;
}
else
{
cout<<"Element is not available on the array."<<endl;
}
return 0;
}
কোড – জাভা
import java.util.Scanner;
public class testingpost
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int i, j, n, mid, srch, Start, End;
System.out.print("How many elements?: ");
n = sc.nextInt();
int [] arr = new int[n+3];
System.out.println("Enter the elements:");
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
System.out.print("Enter the element to search: ");
srch = sc.nextInt();
for(i = 0; i < n; i++)
{
for(j = i + 1; j < n; j++)
{
if(arr[i] > arr[j])
{
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
}
Start = 0; End = n-1;
mid = (Start + End)/2;
while(Start <= End && arr[mid] != srch)
{
if(srch < arr[mid])
{
End = mid-1;
}
else
{
Start = mid+1;
}
mid = (Start + End)/2;
}
if(arr[mid] == srch)
{
System.out.println("Element found at the position: " + mid);
}
else
{
System.out.println("Element is not available on the array.");
}
}
}
আশাকরি আপনারা বাইনারী সার্চ অ্যালগরিদম কিভাবে কাজ করে তা বুঝতে পেরেছেন, এবংএটা কখন ব্যবহার করতে হবে সেটা ও বুঝতে পেরেছেন।
শিমুলের ব্লগ 