'바이너리서치'에 해당되는 글 1건

  1. 2007.09.09 퀵정렬과 이진탐색

#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);
  }


 }

Posted by shunman


티스토리 툴바