#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_SIZE 16001
#define ITERATIONS 8
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))

void sort(int list[], int n);
    
int main() {
    srand(time(NULL));
    int i, j, position, n, k;
    int list[MAX_SIZE];
    int sizelist[]={1,1000,3000,5000,7000,9000,12000,14000};
    clock_t start, stop;
    double duration;
    for(i=0;i<ITERATIONS;i++){
        for(j=0;j<sizelist[i];j++)
            list[j]=rand()%sizelist[i];

        for(j=0; j<sizelist[i]-1; j++){
            for(k=j+1; k<sizelist[i];k++){
                if(list[j]>list[k]){
                    SWAP(list[k], list[j], n);
                }
            }
        }
        
        sort(list, sizelist[i]);
    }
}

void sort(int list[], int n){

    int i, j=rand()%n;
    
    for(i=0; i<n-1;i++)
        if((list[i]==j) || (list[i]<j && list[i+1] >j)){
            printf("%d %d", i, list[i]);
            break;
        }
    if(i==n-1)
        printf("%d %d", i, list[i]);
    printf("\n순차 : %d\n", i);
    
    int min=0, max=n-1;
    int nn=n/2;
    i=0;
    while(min <= max){
        if((nn==0) || (nn>=n) || (list[nn]==j) || (list[nn]<j && list[nn+1] >j)){
            printf("%d %d", nn, list[nn]);
            break;
        }else if(list[nn]>j){
            max=nn-1;
        }else{
            min=nn+1;
        }
        nn=(int)((min+max)/2);
        i++;
    }
    printf("\n이진 : %d\n\n\n\n", i);
}