[태그:] <span>Binary Search Algorithm</span>

동영상 강의에서는 정수 형식 배열에서 이진 탐색 알고리즘을 구현하였습니다.

다음은 C언어로 작성한 이진 탐색 알고리즘 소스 코드입니다.

//common.h
#pragma once //헤더 파일을 한 번만 포함해서 컴파일
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <memory.h>
#include <time.h>
#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

//Book.h
#pragma once
#include "common.h"
#define MAX_TIT_LEN	200
#define MAX_AUT_LEN 20
typedef struct _Book Book;
struct _Book
{
    char title[MAX_TIT_LEN+1];
    char author[MAX_AUT_LEN+1];
    int num;
};

Book *New_Book(const char *title,const char *author,int num);
void Delete_Book(Book *book);
void Book_View(Book *book);
int Book_CompareTitle(Book *book,const char *title);
int Book_CompareAuthor(Book *book,const char *author);
int Book_CompareNum(Book *book,int num);
//Book.c
#include "Book.h"

void Book_Book(Book *book,const char *title,const char *author,int num);
Book *New_Book(const char *title,const char *author,int num)
{
	Book *book = 0;
	book = (Book *)malloc(sizeof(Book));
	Book_Book(book,title,author,num);
	return book;
}
void Book_Book(Book *book,const char *title,const char *author,int num)
{
	memset(book,0,sizeof(Book));
	strncpy(book->title,title,MAX_TIT_LEN);
	strncpy(book->author,author,MAX_AUT_LEN);
	book->num = num;
}
void Delete_Book(Book *book)
{
	free(book);
}
void Book_View(Book *book)
{
	printf("<%010d>:<%s>\n",book->num,book->title);
	printf("\t 저자:%s\n",book->author);
}
int Book_CompareTitle(Book *book,const char *title)
{
	return strcmp(book->title,title);
}
int Book_CompareAuthor(Book *book,const char *author)
{
	return strcmp(book->author,author);
}
int Book_CompareNum(Book *book,int num)
{
	return book->num-num;
}
//Program.c
#include "common.h"
#include "Book.h"
typedef void *Key;
typedef void *Element;
typedef int (*Compare)(Element , Key);

Element *BinarySearch(Element *base,int asize,Key key, Compare compare)
{
    int gap = 0;
    if(asize<=0){ return 0;}

    gap = compare(base[asize/2],key);
    if(gap == 0){ return base+(asize/2); }
    if(gap>0)
    {
        return BinarySearch(base,asize/2,key,compare);
    }
    return BinarySearch(base+(asize/2+1),asize - (asize/2+1),key,compare);
}

#define MAX_BOOK	10
Book *books[MAX_BOOK]={0};
void SimulationInit();
void Simulation();
void SimulationClear();
int main()
{
    SimulationInit();
    Simulation();	
    SimulationClear();
    return 0;
}

void SimulationInit()
{
    int bnum[MAX_BOOK] = {1,4,10,15,20,33,39,40,45,69};
    char title[MAX_TIT_LEN+1]="";
    char author[MAX_AUT_LEN+1]="";
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        sprintf(title,"%010d",rand());
        sprintf(author,"%010d",rand());
        books[i] = New_Book(title,author,bnum[i]);
    }
}
void Simulation()
{
    Book **seat = 0;    
    int key = 0;
    printf("검색할 도서 번호:");
    scanf_s("%d",&key);
    seat = (Book **)BinarySearch(books,MAX_BOOK,(Key)key,(Compare)Book_CompareNum);
    if(seat == 0)
    {
        printf("%d 번 도서 없음\n",key);
    }
    else
    {
        printf("검색 결과:");
        Book_View(*seat);
    }
}


void SimulationClear()
{
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        Delete_Book(books[i]);
    }
}

C언어 알고리즘