बाइनरी सर्च एल्गोरिदम एक ऐसा एल्गोरिदम है जो तुलना और विभाजन तंत्र पर आधारित है। बाइनरी सर्च एल्गोरिदम को आधा-अंतराल खोज, लघुगणक खोज, या बाइनरी चॉप के रूप में भी जाना जाता है। बाइनरी सर्च एल्गोरिदम, एक क्रमबद्ध ऐरे में लक्ष्य मान की स्थिति खोजता है। यह लक्ष्य मान की तुलना ऐरे के मध्य एलिमेंट से करता है। यदि एलिमेंट लक्ष्य एलिमेंट के बराबर है तो एल्गोरिदम पाए गए एलिमेंट का इंडेक्स लौटाता है। और यदि वे बराबर नहीं हैं, तो खोज एल्गोरिदम उस ऐरे के आधे भाग का उपयोग करता है, मान की तुलना के आधार पर, एल्गोरिदम या तो पहले आधे (जब मान मध्य से कम हो) और दूसरे आधे (जब मान मध्य से अधिक हो) का उपयोग करता है। और अगले ऐरे आधे के लिए भी यही करता है।
Input: A[] = {0,2,6,11,12,18,34,45,55,99} n=55 Output: 55 इंडेक्स = 8 पर
व्याख्या
हमारे ऐरे के लिए -
हम 55 की तुलना ऐरे के मध्य एलिमेंट से करेंगे जो 18 है, जो 55 से कम है इसलिए हम ऐरे के दूसरे आधे भाग का उपयोग करेंगे यानी ऐरे {24, 45, 55, 99}, फिर से मध्य 55 है। खोज एलिमेंट के मान की इसके साथ जांच करें। और मान मेल खाता है, तो हम इस मान का इंडेक्स लौटाएंगे जो 8 है।
यदि खोज एलिमेंट मध्य से छोटा होता तो हम पहले आधे का उपयोग करते और तब तक चलते जब तक एलिमेंट ऐरे के मध्य में न मिल जाए।
बाइनरी सर्च को लागू करने के लिए हम कोड को दो तरीकों से लिख सकते हैं। ये दो तरीके केवल उस तरीके में भिन्न हैं जिस तरह से हम उस फ़ंक्शन को कॉल करते हैं जो बाइनरी सर्च एलिमेंट की जांच करता है। वे हैं:
पुनरावृत्ति का उपयोग करके - इसका मतलब है उस फ़ंक्शन के अंदर लूप का उपयोग करना जो मध्य एलिमेंट की समानता की जांच करता है।
पुनरावृत्ति का उपयोग करके - इस विधि में, फ़ंक्शन स्वयं को बार-बार अलग-अलग मानों के सेट के साथ कॉल करता है।
उदाहरण
#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
