C 프로그램의 이진 검색(재귀 및 반복)

이진 검색 정렬된 배열에서 요소(대상 값)의 위치를 ​​찾는 데 사용되는 검색 알고리즘입니다. 이진 검색을 적용하기 전에 배열을 정렬해야 합니다.

이진 검색은 로그 검색, 이진 자르기, 반간 검색 등의 이름으로도 알려져 있습니다.

작업

이진 검색 알고리즘은 배열의 중간 요소로 검색할 요소를 비교하여 작동하고 이 비교를 기반으로 필요한 절차를 따릅니다.

사례 1 − 요소 =중간, 요소가 발견되면 인덱스를 반환합니다.

사례 2 − element> middle, middle+1 인덱스부터 n까지 하위 배열에서 요소를 검색합니다.

사례 3 − element

알고리즘

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