बाइनरी सर्च एक खोज एल्गोरिदम है जिसका उपयोग एक सॉर्टेड ऐरे में किसी तत्व (टारगेट वैल्यू) की स्थिति खोजने के लिए किया जाता है। बाइनरी सर्च लागू करने से पहले ऐरे को सॉर्ट किया जाना चाहिए।
बाइनरी सर्च को इन नामों से भी जाना जाता है: लॉगरिदमिक सर्च, बाइनरी चॉप, हाफ इंटरवल सर्च।
कार्यप्रणाली
बाइनरी सर्च एल्गोरिदम खोजे जाने वाले तत्व की तुलना ऐरे के मध्य तत्व से करके काम करता है और इस तुलना के आधार पर आवश्यक प्रक्रिया का पालन करता है।
केस 1 - तत्व = मध्य, तत्व मिल गया, इंडेक्स लौटाएं।
केस 2 - तत्व > मध्य, मध्य+1 इंडेक्स से n तक सब-ऐरे में तत्व खोजें।
केस 3 - तत्व < मध्य, 0 इंडेक्स से मध्य-1 तक सब-ऐरे में तत्व खोजें।
एल्गोरिदम
पैरामीटर्स: initial_value, end_value
चरण 1: ऐरे का मध्य तत्व खोजें। उपयोग करें: middle = initial_value + end_value / 2; चरण 2: यदि middle = तत्व, तो 'तत्व मिला' और इंडेक्स लौटाएं। चरण 3: यदि middle > तत्व, तो फंक्शन को end_value = middle - 1 के साथ कॉल करें। चरण 4: यदि middle < तत्व, तो फंक्शन को start_value = middle + 1 के साथ कॉल करें। चरण 5: बाहर निकलें।
बाइनरी सर्च एल्गोरिदम फंक्शन का कार्यान्वयन बार-बार फंक्शन को कॉल करता है। यह कॉल दो प्रकार का हो सकता है -
- इटरेटिव (Iterative)
- रिकर्सिव (Recursive)
इटरेटिव कॉल एक ही कोड ब्लॉक को कई बार लूप करना है।
रिकर्सिव कॉल उसी फंक्शन को बार-बार कॉल करना है।
इटरेटिव कॉल का उपयोग करके बाइनरी सर्च लागू करने का प्रोग्राम
उदाहरण
#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element) {
while (start_index <= end_index) {
int middle = start_index + (end_index - start_index) / 2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle - 1;
}
return -1;
}
int main(void) {
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 16;
int found_index = iterativeBinarySearch(array, 0, n - 1, element);
if (found_index == -1) {
printf("Element not found in the array ");
} else {
printf("Element found at index : %d", found_index);
}
return 0;
}
आउटपुट
Element found at index : 4
रिकर्सिव कॉल का उपयोग करके बाइनरी सर्च लागू करने का प्रोग्राम
उदाहरण
#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element) {
if (end_index >= start_index) {
int middle = start_index + (end_index - start_index) / 2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle - 1, element);
return recursiveBinarySearch(array, middle + 1, end_index, element);
}
return -1;
}
int main(void) {
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n - 1, element);
if (found_index == -1) {
printf("Element not found in the array ");
} else {
printf("Element found at index : %d", found_index);
}
return 0;
}
आउटपुट
Element found at index : 3
