뇌를 자극하는 알고리즘 - 6. 탐색 : 이진 탐색(Binary Search)

구현 소스

BinarySearch.h

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Element;

Element BinarySearch(Element Data[], int Size, Element Target);


#endif

----------------------------------------------------------------------------------------
BinarySearch.cpp

#include "BinarySearch.h"

Element BinarySearch(Element Data[], int Size, Element Target)
{
	int Left, Mid, Right;

	Left = 0;
	Right = Size-1;

	while(Left<=Right) // 탐색 범위의 크기가 0이 될때까지 루프를 반복
	{
		Mid = (Left + Right)/2;

		if(Data[Mid] == Target)
		{
			printf("  Search - Data[%d] == %d \n", Mid, Target);
			return 1;
		}
		else if(Target > Data[Mid])
		{ // 기준 Mid의 오른편에 데이터가 존재시
			Left = Mid+1;
		}
		else
		{ // 기준 Mid의 왼편에 데이터가 존재시
			Right = Mid - 1;
		}
	}

	return 0;

}

----------------------------------------------------------------------------------------
main.cpp

#include "BinarySearch.h"


void Rand_Number(Element Data[], int size); // 중복되지 않게 숫자 뽑는 함수
void Print_Arr(Element Data[], int size);   // 배열 요소 전체 출력
int Compare(const void* _elem1, const void* _elem2); // Quick sort


int main()
{
	Element Data[100];
	int Length = sizeof(Data) / sizeof(Element);
	Element* Found;
	Element Target = 30;

	Rand_Number(Data, Length );

	Print_Arr(Data, Length );

	printf("-------------------------------------\n");

	qsort((void*)Data, Length, sizeof(Element), Compare);
	// void qsort( void *base, size_t num, size_t width, int (_cdecl *compare) (const void*, const void*) )
	//   - void *base   : 데이터 집합 배열의 주소
	//   - size_t num   : 데이터 요소의 개수
	//   - size_t width : 한 데이터 요소의 크기
	//   - int (_cdecl *compare) (const void*, const void*) : 비교 함수에 대한 포인터

	Print_Arr(Data, Length );

	printf("-------------------------------------\n");
	BinarySearch(Data,Length,50);		
	printf("-------------------------------------\n");

	printf("bsearch Function - Target Data = %d\n", Target);
	Found = (Element*) bsearch((void*)&Target,(void*)Data, Length, sizeof(Element), Compare);
	// void *bsearch(const void *key, const void *base,  size_t num, size_t width, 
	//             int (_cdecl *compare) (const void*, const void*) )
	//  - const void *key  : 찾고자 하는 목표 값 데이터의 주소
	//  - const void *base : 데이터 집합 배열의 주소
	//   - size_t num   : 데이터 요소의 개수
	//   - size_t width : 한 데이터 요소의 크기
	//   - int (_cdecl *compare) (const void*, const void*) : 비교 함수에 대한 포인터
	//   - 리턴 값 : 데이터 집합 배열에서 목표 값과 동일한 데이터의 주소

	printf("  Search - Data[%d] == %d\n" , ((int)Found-(int)Data) / sizeof(Element) , *Found);
	// 0번 요소의 Data의 주소와 데이터가 존재하는 Found의 주소를 뺀 값으로 배열 인덱스를 구할 수 있음.
	return 0;
}


void Rand_Number(Element Data[], int size)
{
	int i,j;

	srand(time(NULL));

	for( i=0 ; i<size ; i++)
	{
		Data[i] = rand() % size;
		for(j=0; j<i; j++)
		{
			if(Data[j]==Data[i])
			{
				Data[i] = rand() % size;
				j=-1;
				continue;
			}
			
		}
	}

}
void Print_Arr(Element Data[], int size)
{
	int i;
	int count = 0;

	for(i=0 ; i<size; i++)
	{
		if( count % 15 == 0)
			printf("\n");
		printf("%2d, ", Data[i]);
		count++;
	}
	printf("\n");
}

int Compare(const void* _elem1, const void* _elem2)
{
	int* elem1 = (int*)_elem1;
	int* elem2 = (int*)_elem2;

	// 오름차순으로 정렬하도록..

	if(*elem1 > *elem2)
		return 1;
	else if(*elem1 < *elem2)
		return -1;
	else
		return 0;
}

----------------------------------------------------------------------------------------

실행 결과