বাইনারি সার্চ অ্যালগরিদম হলো একটি কমপেয়ার অ্যান্ড স্প্লিট মেকানিজম पर ভিত্তি করে অ্যালগরিদম। বাইনারি সার্চ অ্যালগরিদমকে হাফ-ইন্টারভাল সার্চ, লগারিদমিক সার্চ, বা বাইনারি চপ ও বলা হয়। বাইনারি সার্চ অ্যালগরিদম, একটি সোর্টেড অ্যারেতে টার্গেট ভ্যালুর পজিশন সার্চ করে। এটি টার্গেট ভ্যালুটিকে অ্যারের মাঝপথের এলিমেন্টের সাথে তুলনা করে। যদি এলিমেন্ট টার্গেট এলিমেন্টের সমান হয়, তবে অ্যালগরিদম ফাউন্ড এলিমেন্টের ইনডেক্স রিটার্ন করে। এবং যদি সমান না হয়, তবে সার্চিং অ্যালগরিদম অ্যারের অর্ধেক অংশ ব্যবহার করে, তুলনার ভ্যালু বেসডে, অ্যালগরিদম অথবা প্রথম অর্ধেক অংশ ব্যবহার করে (যখন ভ্যালু মাঝপথের চেয়ে কম) অথবা দ্বিতীয় অর্ধেক অংশ (যখন ভ্যালু মাঝপথের চেয়ে বেশি)। এবং পরবর্তী অ্যারের অর্ধেক অংশে একই কাজ করে।
Input: A[] = {0,2,6,11,12,18,34,45,55,99} n=55 Output: 55 at Index = 8
ব্যাখ্যা
আমাদের অ্যারের জন্য -
৫৫ কে অ্যারের মাঝপথের এলিমেন্ট ১৮ দিয়ে তুলনা করব, যা ৫৫-র চেয়ে ছোট, তাই আমরা অ্যারের দ্বিতীয় অর্ধেক অংশ ব্যবহার করব অর্থাৎ {24, 45, 55, 99}, আবার মাঝপথ ৫৫। সার্চ এলিমেন্টের ভ্যালু সেটির সাথে চেক করব। এবং ভ্যালু মেললে, আমরা এই ভ্যালুর ইনডেক্স রিটার্ন করব যা ৮।
যদি সার্চ এলিমেন্ট মাঝপথের চেয়ে ছোট হতো, তবে আমরা প্রথম অর্ধেক অংশ ব্যবহার করতাম এবং এভাবেই চলতাম যতক্ষণ না এলিমেন্ট অ্যারের মাঝপথে মিলে যায়।
বাইনারি সার্চ বাস্তবায়ন করার দুটি পদ্ধতি আছে। এই দুটি পদ্ধতি শুধু ফাংশন কল করার পদ্ধতিতে ভিন্ন যেটি বাইনারি সার্চ এলিমেন্ট চেক করে। সেগুলো হলো:
ইটারেশন ব্যবহার করে− অর্থাৎ ফাংশনের ভেতরে লুপ ব্যবহার করে মাঝপথের এলিমেন্টের সমানতা চেক করা।
রিকার্শন ব্যবহার করে এই পদ্ধতিতে, ফাংশন নিজেরাই বারবার ভিন্ন সেট ভ্যালু দিয়ে কল করে।
উদাহরণ (ইটারেটিভ)
#include<stdio.h> int iterativeBsearch(int A[], int size, int element); int main() { int A[] = {0,12,6,12,12,18,34,45,55,99}; int n=55; printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n)); return 0; } int iterativeBsearch(int A[], int size, int element) { int start = 0; int end = size-1; while(start<=end) { int mid = (start+end)/2; if( A[mid] == element) { return mid; } else if( element < A[mid] ) { end = mid-1; } else { start = mid+1; } } return -1; }
আউটপুট
55 is found at Index 8
উদাহরণ (রিকার্সিভ)
#include<stdio.h> int RecursiveBsearch(int A[], int start, int end, int element) { if(start>end) return -1; int mid = (start+end)/2; if( A[mid] == element ) return mid; else if( element < A[mid] ) RecursiveBsearch(A, start, mid-1, element); else RecursiveBsearch(A, mid+1, end, element); } int main() { int A[] = {0,2,6,11,12,18,34,45,55,99}; int n=55; printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n)); return 0; }
আউটপুট
55 is found at Index 8
