이진 탐색(Binary Search)

이진 탐색 알고리즘은 정렬된 배열에서만 사용 가능하다.

아주 많은 데이터가 저장되어 있는 배열에서 순차탐색보다 효과적으로 값을 찾을 수 있다.

기본 원리는 배열에서 중간 위치를 기준으로  찾고자 하는 값이 더 작으면 중간 위치의 왼쪽에서 계속 탐색,

찾고자 하는 값이 더 크면 중간 위치보다 오른쪽에 있는 값들을 탐색하며,

다음 위치는 계속 남은 배열의 중간위치를 기준으로 탐색한다.

위 그림의 예시에서 1부터 10까지 저장된 배열에서 2를 찾을 것이다.

초기값으로 front = 0, rear = 9가 되며, mid = (0 + 9 ) / 2 = 4 를 가진다.

mid인덱스에서 가지고 있는 값은 5이므로, 찾고자 하는 숫자가 더 작다. 

그러므로 rear의 값을 mid - 1로 바꿔서 다시 탐색한다.

그러면 front = 0, rear = 3, mid = 1이 된다.

1번 인덱스는 2이므로, 찾고자하는 숫자와 일치하므로 이진 탐색을 종료한다.

반복문을 사용하는 방법과, 재귀호출을 통한 구현이 모두 가능하다.

일반적으로는 반복문을 사용해서 구현하면 된다.

//Binary Search
#include <stdio.h>
 
int binarySearchRecursion(int number[], int front, int rear, int target)
{
    int mid = (front + rear) / 2;
 
    if (front > rear)//배열에서 탐색하지 못함
    {
        return -1;
    }
 
    if (number[mid] == target)//찾은 경우
    {
        return mid;
    }
    else if (number[mid] < target)//찾고자 하는 값이 더 크므로 오른쪽 탐색
    {
        return binarySearchRecursion(number, mid + 1, rear, target);
    }
    else//찾고자 하는 값이 더 작으므로 왼쪽 탐색
    {
        return binarySearchRecursion(number, front, mid - 1, target);
    }
}
 
int binarySearchIteration(int number[], int size, int target)
{
    int front = 0;
    int rear = size-1;
    int mid;
 
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (number[mid] == target)//찾은 경우
        {
            return mid;
        }
 
        if (number[mid] < target)
        {//찾는 값이 더 크므로 mid를 기준으로 오른쪽 탐색
            front = mid + 1;
        }
        else // if(number[mid] > target)
        {//찾는 값이 더 작으므로 mide를 기준으로 왼쪽 탐색
            rear = mid - 1;
        }
    }
    //찾지 못하고 while문이 종료되면 실패 반환
    return -1;
}
 
int main(void)
{
    int number[200];
 
    for (int i = 0; i < 200; i++)
        number[i] = i + 1;
 
    int findNum = 201;
 
    printf("Binary Search Iterative\n");
    int index = binarySearchIteration(number, sizeof(number) / sizeof(int), findNum);
    if(index!=-1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    printf("Binary Search Recursive\n");
    index = binarySearchRecursion(number, 0, (sizeof(number) / sizeof(int)) - 1, findNum);
    if (index != -1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    return 0;
}