C 프로그램에서 이진 검색(재귀 및 반복) 구현

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

이진 검색은 로그 검색, 이진 검색, 반간격 검색이라고도 합니다.

작동 방식

이진 검색 알고리즘은 검색할 요소를 배열의 중간 요소와 비교하여 작동하며 이 비교 결과에 따라 필요한 프로세스를 수행합니다.

사례 1 - 요소 = 중간 값, 요소를 찾아 인덱스를 반환합니다.

사례 2 - 요소 > 중간 값, 중간 +1부터 n까지 인덱스가 지정된 하위 배열에서 요소를 검색합니다.

사례 3 - 요소

Algorithm

매개변수 초기값, 종료값

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
• recursive

반복 호출은 동일한 코드 조각을 여러 번 반복합니다.

재귀 호출은 동일한 함수를 반복적으로 호출하는 것입니다. 반복적 인 Calls

exampling

r

#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;
}

output

Element found at index : 4

a 프로그램을 사용하여 이진 검색을 구현하는 프로그램은 재귀 콜 콜 콜을 사용하여 이진 검색을 구현하는 프로그램 프로그램

위 내용은 C 프로그램에서 이진 검색(재귀 및 반복) 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!