सी प्रोग्राम में बाइनरी सर्च (पुनरावर्ती और पुनरावृत्त)

द्विआधारी खोज एक खोज एल्गोरिथम है जिसका उपयोग क्रमबद्ध सरणी में किसी तत्व (लक्ष्य मान) की स्थिति खोजने के लिए किया जाता है। बाइनरी खोज लागू करने से पहले सरणी को क्रमबद्ध किया जाना चाहिए।

बाइनरी सर्च को इन नामों से भी जाना जाता है, लॉगरिदमिक सर्च, बाइनरी चॉप, हाफ इंटरवल सर्च।

कार्यरत

द्विआधारी खोज एल्गोरिथ्म सरणी के मध्य तत्व द्वारा खोजे जाने वाले तत्व की तुलना करके काम करता है और इस तुलना के आधार पर आवश्यक प्रक्रिया का पालन करता है।

केस 1 -तत्व =मध्य, तत्व पाया जाता है और सूचकांक लौटाता है।

केस 2 -तत्व> मध्य, मध्य+1 अनुक्रमणिका से n तक उप-सरणी में तत्व की खोज करें।

केस 3 -तत्व <मध्य, 0 अनुक्रमणिका से मध्य -1 तक उप-सरणी में तत्व की खोज करें।

एल्गोरिदम

पैरामीटर inital_value , end_value

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

बाइनरी सर्च एल्गोरिथम फ़ंक्शन का कार्यान्वयन बार-बार कार्य करने के लिए कॉल का उपयोग करता है। यह कॉल दो प्रकार की हो सकती है -

• पुनरावर्ती
• पुनरावर्ती

पुनरावर्ती कॉल कोड के एक ही ब्लॉक पर कई बार लूप कर रहा है ]

पुनरावर्ती कॉल एक ही फ़ंक्शन को बार-बार कॉल कर रहा है।

इटरेटिव कॉल का उपयोग करके बाइनरी खोज को लागू करने का कार्यक्रम

उदाहरण

#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