Find a lost number in O(N) better than O(NlogN) by sort.

find_a_lost_number.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

double print_time(struct timeval *s, struct timeval *e){
        int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
        int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
        return (double)(ei-si)/1000.0;
}

int compare_int(const void *a, const void*b){
    return *(int*)a-*(int*)b;
}

void debug(int c, int* data){
    if(c>100) return;
    int i;
    for(i=0;i<c;i++){
        printf("%d,",data[i]);
    }
    printf("\n");
}

int find(int num, int low, int high,int* data){
    //debug(num,data);

    int mid = low+(high-low)/2;
    if(num==0) return mid;
    if(num==1){
        if(*data==mid) return high;
        else return mid;
    }

    int* below = malloc(sizeof(int)*(num/2+1));
    int* above = malloc(sizeof(int)*(num/2+1));
    int cb = 0;
    int ca = 0;

    int i;
    //printf("low,mid,high = %d,%d,%d\n",low,mid,high);
    for(i=0;i<num;i++){
        if(data[i]<mid){
            below[cb++]=data[i];
        }else{
            above[ca++]=data[i];
        }
    }

    if(cb<(mid-low)){
        return find(cb,low,mid-1,below);
    }else{
        return find(ca,mid,high,above);
    }
}

void scramble(int c, int* data){
    srand((unsigned)time(NULL));
    int i,m,n,t;
    m = 0;
    // Scramble twice longer than the size
    for(i=0;i<c*2;i++){
        t = data[m];
        n = rand()%c;
        data[m] = data[n];
        data[n] = t;
        m = n;
    }
}

void func_O_N(int c, int* data){
    int deleted = data[c-1];
    int found   = find(c-1,1,c,data);

    printf("%d==%d:%s\n",deleted,found,deleted==found?"OK":"NG");
}

void func_O_NlogN(int c, int* data){
    int deleted = data[c-1];
    int found = 0;

    qsort(data,c-1,sizeof(int),compare_int);

    int i;
    for(i=0;i<c-1;i++){
        if(data[i]!=i+1){
            found = i+1;
            break;
        }
    }
    if(found==0) found=c;
    printf("%d==%d:%s\n",deleted,found,deleted==found?"OK":"NG");

}


int main(int argc, char* argv[]){
    if(argc!=2) exit(1);
    int c = atoi(argv[1]);
    int* data = malloc(sizeof(int)*c);
    int i;
    for(i=0;i<c;i++){
        //*data++ = i;
        data[i] = i+1;
    }
    scramble(c,data);

    struct timeval s, e;

    gettimeofday(&s,NULL);
    func_O_N(c,data);
    gettimeofday(&e,NULL);
    printf("func_O_N : %.2lf sec.\n",print_time(&s,&e));

    gettimeofday(&s,NULL);
    func_O_NlogN(c,data);
    gettimeofday(&e,NULL);
    printf("func_O_NlogN : %.2lf sec.\n",print_time(&s,&e));

    return 0;
}