C언어] 검색-이진검색

[이진검색]

1. 이진 검색(Binary Search)이란?
이진 검색은 정렬된 배열에서 중간 값을 찾아 원하는 항목을 찾는 효율적인 알고리즘이다.

이진 검색은 구간의 중간값과 키값의 대소를 구분하여 테이블을 절반씩 나눠가며 비교하는 방법으로 한번 비교할 때마ㅏ다 테이블의 길이가 절반씩 줄어들기 때문에 검색 효율이 좋고 테이블이 웬만큼 커도 느려지지 않는다.

#include <stdio.h>
 
//& 이진 검색 함수
int binarySearch(int arr[], int low, int high, int target)
{
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] == target)
        {
            return mid;  //& 찾은 경우 해당 인덱스 반환
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
 
    return -1;  //& 찾지 못한 경우 -1 반환
}
 
int main()
{
    int arr[] = { 2, 5, 8, 12, 16, 23, 38, 45, 50 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 16;
 
    //& 이진 검색 수행
    int result = binarySearch(arr, 0, size - 1, target);
 
    if (result != -1)
    {
        printf("원소 %d은 배열의 인덱스 %d번째 있습니다.\n", target, result);
    }
    else
    {
        printf("원소를 찾을 수 없습니다.\n");
    }
 
    return 0;
}// main