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