การค้นหาไบนารี (แบบเรียกซ้ำและวนซ้ำ) ในโปรแกรม C

การค้นหาแบบไบนารี เป็นอัลกอริธึมการค้นหาที่ใช้เพื่อค้นหาตำแหน่งขององค์ประกอบ (ค่าเป้าหมาย) ในอาร์เรย์ที่จัดเรียง ควรจัดเรียงอาร์เรย์ก่อนที่จะใช้การค้นหาแบบไบนารี

การค้นหาไบนารียังเป็นที่รู้จักในชื่อเหล่านี้ การค้นหาลอการิทึม สับไบนารี การค้นหาแบบครึ่งช่วง

การทำงาน

อัลกอริธึมการค้นหาแบบไบนารีทำงานโดยการเปรียบเทียบองค์ประกอบที่จะค้นหาโดยองค์ประกอบตรงกลางของอาร์เรย์ และตามการเปรียบเทียบนี้จะเป็นไปตามขั้นตอนที่จำเป็น

กรณีที่ 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.

การใช้งานฟังก์ชันอัลกอริธึมการค้นหาแบบไบนารีใช้การเรียกทำงานซ้ำแล้วซ้ำอีก การโทรนี้สามารถเป็นได้สองประเภท -

• ทำซ้ำ
• เรียกซ้ำ

โทรซ้ำ กำลังวนซ้ำบนบล็อกโค้ดเดียวกันหลายครั้ง ]

โทรซ้ำ กำลังเรียกใช้ฟังก์ชันเดิมซ้ำแล้วซ้ำอีก

โปรแกรมเพื่อใช้การค้นหาแบบไบนารีโดยใช้ ITERATIVE CALL

ตัวอย่าง

#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