이진 검색 알고리즘을 사용한 C 언어 예제
추천 자료: ASP.NET Core 인증 및 권한 부여
이진 검색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾을 수 있는 효율적인 알고리즘입니다. 이번 포스트에서는 C 언어를 사용하여 이진 검색 알고리즘을 구현한 예제를 살펴보겠습니다.
코드: binary_search_example.c
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
// 정수 비교를 위한 사용자 정의 함수
int compare_integers(const void* value1, const void* value2)
{
return (*(int*)value1 - *(int*)value2);
}
// 배열 출력을 위한 함수
void print_array(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void)
{
int search_key = 5; // 찾고자 하는 값
int* found_value; // 검색 결과를 저장할 포인터
int numbers[5] = { 45, 12, 5, 89, 27 }; // 검색 대상 배열
printf("정렬 전: ");
print_array(numbers, 5); // 정렬 전 배열 출력
// 배열을 오름차순으로 정렬
qsort(numbers, 5, sizeof(numbers[0]), compare_integers);
printf("정렬 후: ");
print_array(numbers, 5); // 정렬 후 배열 출력
// 이진 검색 수행 (찾고자 하는 값, 배열, 배열 크기, 배열 원소 크기, 비교 함수)
found_value = bsearch(&search_key, numbers, 5, sizeof(numbers[0]), compare_integers);
// 검색 결과 출력
if (found_value)
{
printf("%d를 %ld번 위치에서 찾았습니다.\n", search_key, found_value - numbers);
}
else
{
printf("%d를 찾지 못했습니다.\n", search_key);
}
return 0;
}
정렬 전: 45 12 5 89 27
정렬 후: 5 12 27 45 89
5를 0번 위치에서 찾았습니다.
이 예제에서는 이진 검색 알고리즘을 사용하여 정렬된 배열에서 원하는 값을 찾습니다. 먼저, 정수를 비교하는 사용자 정의 함수 compare_integers
를 작성합니다. 이 함수는 qsort
와 bsearch
함수에서 사용됩니다.
다음으로, 배열을 출력하는 print_array
함수를 작성합니다. 이 함수는 배열의 요소를 출력하고, 줄바꿈 문자를 추가합니다.
main
함수에서는 다음과 같은 작업을 수행합니다:
- 찾고자 하는 값을 정의합니다.
- 검색 대상이 되는 배열을 정의합니다.
- 배열을 정렬합니다. 이진 검색은 정렬된 배열에서만 작동하므로, 배열을 먼저 정렬해야 합니다.
- 이진 검색을 수행합니다.
bsearch
함수는 찾고자 하는 값, 배열, 배열 크기, 배열 원소 크기, 비교 함수를 인자로 받습니다.bsearch
는 검색에 성공하면 찾은 값을 가리키는 포인터를 반환하고, 실패하면 NULL을 반환합니다. - 검색 결과를 출력합니다.
found_value
포인터가 NULL이 아닌 경우, 찾은 값을 출력하고, 그 위치를 계산하여 출력합니다. NULL인 경우, 원하는 값을 찾지 못했음을 출력합니다.
이 예제를 통해 이진 검색 알고리즘을 사용하여 정렬된 배열에서 원하는 값을 빠르게 찾는 방법을 이해할 수 있습니다. 이진 검색 알고리즘은 효율적이고 빠른 검색 방법으로, 컴퓨터 과학 및 프로그래밍에서 널리 사용되는 기초 알고리즘 중 하나입니다.
추천 자료: .NET Blazor에 대해 알아보시겠어요? .NET Blazor 알아보기를 확인해보세요!