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

이진 검색 알고리즘은 비교 및 ​​분할 메커니즘을 기반으로 하는 알고리즘입니다. 이진 검색 알고리즘은 반마진 검색, 로그 검색 또는 이진 검색이라고도 합니다. 정렬된 배열에서 대상 값의 위치를 ​​찾는 이진 검색 알고리즘입니다. 대상 값을 배열의 중간 요소와 비교합니다. 요소가 대상 요소와 동일한 경우 알고리즘 은 발견된 요소의 인덱스 를 반환합니다. 동일하지 않은 경우 검색 알고리즘은 값의 비교에 따라 배열의 절반을 사용하고 알고리즘은 첫 번째 절반(값이 중간보다 작은 경우)과 두 번째 절반(값이 중간보다 작은 경우)을 사용합니다. 중간) 및 후반부(값이 중간보다 큰 경우). 배열의 다음 절반에도 동일한 작업을 수행합니다.

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

설명

우리 배열의 경우 -

55를 배열 18의 중간 요소인 55보다 작은 것과 비교할 것이므로 배열의 후반부인 배열 {24, 45, 55, 99} , 가운데도 55 입니다. 검색 요소의 값을 확인하는 데 사용합니다. 그리고 일치하는 값이 있으면 값의 인덱스를 8로 반환합니다.

검색 요소가 중간보다 작으면 전반부를 사용하고 요소가 배열 중간에서 발견될 때까지 계속됩니다.

이진 검색을 구현하기 위해 두 가지 방법으로 코드를 작성할 수 있습니다. 이 두 가지 방법은 이진 검색 요소를 확인하는 함수를 호출하는 방식과만 다릅니다.

• 반복 사용 - 이는 중간 요소의 동등성을 확인하기 위해 함수 내부의 루프를 사용하는 것을 의미합니다. < /p>

• Using 이 방법에서 함수는 다른 값 세트를 사용하여 자신을 계속해서 호출합니다.

예

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

출력

55 is found at Index 8

예

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

출력

55 is found at Index 8

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