[C코드] :: BINARY SEARCH code (이진 탐색 코드)

BINARY SEARCH (이진탐색)

What is it?

• Binary search(이진탐색). 많은 탐색기법 중 간단하고 속도가 빨라 자주 쓰이는 로직이다.
• 배열을 계속 반으로 갈라 UP/DOWN을 하면서 (1/2)ⁿ개로 줄여가며 탐색한다.
• 반드시 정렬된 배열에서만 사용할 수 있다.
• Worst Case, 'O( logn )'
• 너무 간단한 코드라 자세한 설명은 생략한다.

CODE

/************************************************
 * BINARY SEARCH  ******************************
 * ********************************* binaryS.c ****
 * ***********************************************/

#include <stdio.h>


/* Length of Array */
#define MAX_BUFF 5


/* Data which into Array */
typedef struct DATA
{
    int mKey;             // 키
    int mValue;         // 값
} DATA;


/****************************** *
 * BINARY SEARCH by Recursive *
 * ***************************** */
int BinarySearch(struct DATA aSortedArray[], int aBegin, int aEnd, int aFind)
{
    /* Arguments */
    // aSortedArray[] : 정렬된 배열
    // aBegin : 배열의 0번째 인덱스
    // aEnd : 배열의 끝 인덱스
    // aFind : 찾고자 하는 값 X
    
    /* Array's middle index */
    int mMid = 0;

    /* Escape condition */
    if ( aBegin > aEnd )
    {
        return -1;
    }

    /* Declare mMid's value */
    mMid = ( aBegin + aEnd ) / 2;

    /* If i find the value X, */
    if ( aSortedArray[mMid].mValue == aFind )
    {
        /* Return */
        return mMid;
    }

    /* If arry[mid] > X */
    else if ( aSortedArray[mMid].mValue > aFind )
    {
        /* Recursive, aEnd is mMid-1 */
        return BinarySearch( aSortedArray, aBegin, mMid-1, aFind );
    }

    /* If arry[mid] < X */
    else if ( aSortedArray[mMid].mValue < aFind )
    {
        /* Recursive, aBegin is mMid+1 */
        return BinarySearch( aSortedArray, mMid+1, aEnd, aFind );
    }
    
}




/* MAIN FUNCTION */
int main()
{
    /* declare an Array which has struct datas */
    struct DATA arr[MAX_BUFF];

    /* Variables */
    int mFindValue = 0;      // 입력받는 찾을 값
    int mIndex = 0;               // 찾은 값의 인덱스
    int inputKey = 0;            // 배열에 들어갈 입력받은 key값
    int inputValue = 0;        // 배열에 들어갈 입력받은 value값
    

    printf("\nEnter the 5 KEYs and VALUEs which you want : \n");
    printf("\n\n :::: WARNING : YOU MUST ENTER BY ORDER FOR VALUEs::::\n\n");
    for(int i = 0; i < MAX_BUFF; i++)
    {
        /* Fill the Array with inputed values */
        scanf("%d", &inputKey);
        scanf("%d", &inputValue);
        arr[i].mKey = inputKey;
        arr[i].mValue = inputValue;
        printf("KEY : %d     VALUE : %d     and\n", inputKey, inputValue);
    }
    
    printf("\n\nThen, current array's status is : \n\n");
    printf("Keys   : [ ");
    for(int i = 0; i < MAX_BUFF; i++)
    {
        printf("%d ", arr[i].mKey);
    }
    printf("]\n");
    printf("VALUEs : [ ");
    for(int i = 0; i < MAX_BUFF; i++)
    {
        printf("%d ", arr[i].mValue);
    }
    printf("]\n\n\n");
    while(mFindValue!=999)
    {
        printf("Enter the number which you wanna find (if you want to exit it, enter '999' : ");
        scanf("%d", &mFindValue);
        if(mFindValue==999)
        {
            printf("\n\nExit................\n\n");
            break;
        }
        else
        {
            /* SEARCH */
            mIndex = BinarySearch(arr, 0, MAX_BUFF-1, mFindValue);
            if(mIndex < 0)
            {
                printf("There is no %d in this array. \n\n", mFindValue);
            }
            else
            {
                printf("\n%d is in Array[ %d ]  and  %d's KEY is %d\n\n",
                       mFindValue, mIndex, mFindValue, arr[mIndex].mKey);
            }
        }
    }
    return 0;
}