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

void sort();
    
int main() {
    srand(time(NULL));
    int i, j, position;
    int list[MAX_SIZE];
    int sizelist[]={0, 100, 200,300,400,500,600,700,800,900,1000,200,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000};
    clock_t start, stop;
    double duration;
    printf("  n  time\n");
    for(i=0;i<ITERATIONS;i++){
        for(j=0;j<sizelist[i];j++)
            list[i]=rand()%100;

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

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

    int j=rand()%n;
    
    for(int i=0; i<n;i++)
        if((n==0) || (n>=98) || (list[n]==j) || (list[n]<j && list[n+1] >j)){
            printf("%d %d", n, list[n]);
            break;
        }
    
    n=n/2;
    scanf("%d", &j);
    int min=0, max=99;
    while(1){
        if((n==0) || (n>=98) || (list[n]==j) || (list[n]<j && list[n+1] >j)){
            printf("%d %d", n, list[n]);
            break;
        }else if(list[n]>j){
            max=n+1;
        }else{
            min=n-1;
        }
        n=(int)((min+max)/2);
    }
}

int main() {
    srand(time(NULL));

    int list[100];
    int i, j;
    
    for(i=0;i<100;i++){
        list[i]=rand()%100;
    }
    int n;
    for(j=0; j<99; j++){
        for(i=j+1; i<100;i++){
            if(list[j]>list[i]){
                n=list[j];
                list[j]=list[i];
                list[i]=n;
            }
        }
    }

     for(i=0;i<100;i++){
        printf("%d   %d\n", i, list[i]);
    }

    printf("\n----------------\n");
    n=50;
    scanf("%d", &j);
    int min=0, max=99;
    while(1){
        if((n==0) || (n>=98) || (list[n]==j) || (list[n]<j && list[n+1] >j)){
            printf("%d %d", n, list[n]);
            break;
        }else if(list[n]>j){
            max=n+1;
        }else{
            min=n-1;
        }
        n=(int)((min+max)/2);
    }
    
    return 0;
}