#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
#define MAX_SIZE 1000
int list[MAX_SIZE];
int n;
int key;
int binary_result;
void quick_sort(int,int );
int Binary_Search(int);
void main()
{
char ch;
int i;
int counter=0;
int max=0;
clock_t a,b;
printf("Number of Records = ");
scanf("%d",&n);
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
{
list[i] = (rand()*rand())%1000;
// printf("%d ",list[i]);
}
a=clock();
quick_sort(0,n-1);
b=clock();
printf("Excuteion Duration = %f\n",(double)(b-a)/CLK_TCK);
for(i=0;i<n;i++)
{
printf("%d ",list[i]);
}
printf("input the key\n");
scanf("%d",&key);
printf("key value is %d\n",key);
printf("\n");
printf("this is sequentiol search\n");
for(i=0;i<n;i++)
{
counter++;
if(list[i]==key)
{
printf("값을 %d번째 검색에서 찾았습니다\n",counter);
break;
}
}
if(i==n)
{
printf("Not found\n");
}
printf("\n");
printf("this is Binary Search\n");
binary_result = Binary_Search(key);
if(binary_result!=-1)
{
printf("value is %d\n",binary_result);
}
getchar(ch);
}
int Binary_Search(int mid_key) //mid_key는 찾고자 하는 값(main 함수에서 key변수)
{
int left=0;
int right = n-1;
int binary_count=0;
int middle;
while(left<right)
{
binary_count++;
middle= (left+right)/2;
if(list[middle]>mid_key)
{
right= middle-1;
}
else if(list[middle]<mid_key)
{
left = middle+1;
}
else
{
return middle;
}
}
return -1;
}
void quick_sort(int left,int right)
{
int pivot, i,j,temp;
if(left<right)
{
i=left; j=right+1; pivot=list[left];
do
{
do
i++;
while(list[i]<pivot);
do
j--;
while(list[j]>pivot);
if(i<j) SWAP(list[i],list[j],temp);
}
while(i<j);
SWAP(list[left],list[j],temp);
quick_sort(left,j-1);
quick_sort(j+1,right);
}
}
