#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COMPARE(mid,searchnum) (((mid)<(searchnum)) ? (-1) : (((mid)>(searchnum)) ? (1) : (0))) //미들값과 찾는값의 크기를 비교하여 해당 값 반환
/* mid<searchnum 이면 -1 반환, mid>searchnum이면 1 반환, mid=searchnum이면 1 반환*/
#define MAX_SIZE 1001 //상수 MAX_SIZE는 1001
#define ITERATIONS 16 //상수 ITERATIONS는 16
int binsearch_rec(int list[], int searchnum, int left, int right);
int binsearch_itr(int list[], int searchnum, int left, int right);
int main(void)
{
int i,j,position; //int형 변수 i,j,positon 선언
int list[MAX_SIZE]; //int형 배열 list 선언, 배열의 크기는 MAX_SIZE=1001
int sizelist[]={0,10,20,30,40,50,60,70,80,90,100,200,400,600,800,1000}; //이진탐색을 시행할 크기
int numtimes[]={3000000,1200000,600000,500000,400000,400000,400000,300000,300000,200000,200000,100000,50000,50000,50000,20000}; // 이진탐색을 돌릴 횟수
clock_t start, stop; //clock_t는 time.h에서 정의되어있는데 long 형과 같다. start, stop 변수 선언
double duration, total; //double 형 변수 duration, total 선언
for(i=0;i<MAX_SIZE;i++)
{
list[i]=i; //각 배열의 원소의 값을 번호로 초기화
}
printf("=====================ITERATIVE=====================\n");
printf("sizelist[i] numtimes[i] stop-start total duration positon\n");
for(i=0;i<ITERATIONS;i++)
{
start=clock(); //start에 프로그램이 시작될 때부터 지난 틱수 저장
for(j=0;j<numtimes[i];j++) // j=0부터 numtimes[i] 미만까지 반복
{
position=binsearch_itr(list,sizelist[i]+1,0,sizelist[i]); //positon에 binseasrch_itr함수의 반환값 저장 최악의 경우로 없는 숫자를 찾는다.
//예를들어 sizelist[2]면 searchnum은 0에서 10사이에서 11을 찾는 것이다. 리턴은 -1일 것이다.
}
stop=clock(); //stop에 프로그램이 시작될 때부터 지난 틱수 저장
total=((double)(stop-start))/CLOCKS_PER_SEC; //CLOCKS_PER_SEC는 초당 클락수이다.1000으로 정의되어 있다. stop-start=사이의 클락수이므로 연산을 하면 시간(초)가 반환된다.
duration=(total/numtimes[i]); //total을 numtimes[i]로 나눈 값
printf("%11d %11d %11d %11f %11f %11d\n",sizelist[i],numtimes[i],(int)(stop-start),total,duration,position); //화면에 각각의 값을 11자리씩 출력
list[sizelist[i]]=sizelist[i]; //reset value 라고 써있는데 왜 있는지 잘 모르겠다.
}
printf("=====================RECURSIVE=====================\n");
printf("sizelist[i] numtimes[i] stop-start total duration positon\n");
for(i=0;i<ITERATIONS;i++)
{
start=clock(); //start에 프로그램이 시작될 때부터 지난 틱수 저장
for(j=0;j<numtimes[i];j++)// j=0부터 numtimes[i] 미만까지 반복
{
position=binsearch_rec(list,sizelist[i]+1,0,sizelist[i]); //positon에 binseasrch_rec함수의 반환값 저장 최악의 경우로 없는 숫자를 찾는다.
//예를들어 sizelist[2]면 searchnum은 0에서 10사이에서 11을 찾는 것이다. 리턴은 -1일 것이다.
}
stop=clock(); //stop에 프로그램이 시작될 때부터 지난 틱수 저장
total=((double)(stop-start))/CLOCKS_PER_SEC; //CLOCKS_PER_SEC는 초당 클락수이다.1000으로 정의되어 있다. stop-start=사이의 클락수이므로 연산을 하면 시간(초)가 반환된다.
duration=(total/numtimes[i]); //total을 numtimes[i]로 나눈 값
printf("%11d %11d %11d %11f %11f %11d\n",sizelist[i],numtimes[i],(int)(stop-start),total,duration,position); //화면에 각각의 값을 11자리씩 출력
list[sizelist[i]]=sizelist[i]; //reset value 라고 써있는데 왜 있는지 잘 모르겠다.
}
return 0;
}
int binsearch_itr(int list[], int searchnum, int left, int right) //반복적으로 짠 이진탐색
{
int middle; //int형 변수 middle 선언
while(left<=right) //left가 right 이하일때 반복
{middle=(left+right)/2; //미들은 left와 right의 산술평균
switch(COMPARE(list[middle],searchnum)) //COMPARE 의 값을 받아와 그에 따라 switch-case로 판단
{
case -1 : left=middle+1;
break; //-1경우 left에 middle+1로 대입 후 break
case 0 : return middle;
break; //0경우 middle값 리턴 후 break
case 1 : right=middle-1;
break; //1경우 right에 middle-1로 대입 후 break
}
}
return -1; //while 루프가 깨졌을 경우 반환값 -1
}
int binsearch_rec(int list[], int searchnum, int left, int right) //recursive function으로 짠 이진탐색
{
int middle;//int형 변수 middle 선언
while(left<=right)//left가 right 이하일때 반복 recursive function이라서 if 를 써도 무방하다.
{middle=(left+right)/2;//미들은 left와 right의 산술평균
switch(COMPARE(list[middle],searchnum)) //COMPARE 의 값을 받아와 그에 따라 switch-case로 판단
{
case -1 : return binsearch_rec(list,searchnum,middle+1,right);
break; //-1경우 binsearch_rec함수의 left자리에 middle+1, right 인자에 right 넣어 호출 후 break
case 0 : return middle;
break; //0의 경우 middle값 리턴 후 break
case 1 : return binsearch_rec(list,searchnum,left,middle-1);
break; //1경우 binsearch_rec함수의 left자리에 left, right 인자에 middle-1 넣어 호출 후 break
}
}
return -1; //while 루프가 깨졌을 경우 반환값 -1
}
