Linear vs binary vs interpolation search

searches.c

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

int compar(const void *a, const void *b) {
    unsigned int val_a = *(unsigned int *)a;
    unsigned int val_b = *(unsigned int *)b;
    if (val_a < val_b) {
        return -1;
    } else if (val_a == val_b) {
        return 0;
    } else {
        return 1;
    }
}

unsigned int * generateArray(int size) {
    unsigned int *array = malloc(size * sizeof(int));
    arc4random_buf(array, size * sizeof(int));
    qsort(array, size, sizeof(unsigned int), compar);
    
    return array;
}

int linearSearch(unsigned int *array, int size, unsigned int searchNum) {
    for (int i = 0; i < size; i++) {
        if (array[i] == searchNum) {
            return i;
        }
    }
    return -1;
}

int binarySearch(unsigned int *array, int size, unsigned int searchNum) {
    int low = 0;
    int high = size;
    while (low != high) {
        int med = (high-low)/2 + low;
        int val = array[med];
        if (val < searchNum) {
            low = med;
        } else if (val > searchNum) {
            high = med;
        } else {
            return med;
        }
    }
    return -1;
}

#ifdef DEBUG
int first_time = 1;
#endif

int interpolationSearch(unsigned int *array, int size, unsigned int searchNum) {
    int guess = ((long)searchNum * size)/UINT_MAX;
    int val = array[guess];
    int error = searchNum - val;
    
    int guesses = 0;
    
#ifdef DEBUG
    if (first_time) {
        printf("initial guess is %d, error is %d\n", guess, error);
    }
#endif
    
    while (abs(error) > 1000 && guesses < 3) {
        guess += ((long)error * size)/UINT_MAX;
        val = array[guess];
        error = searchNum - val;
        
#ifdef DEBUG
        if (first_time) {
            printf("new guess is %d, error is %d\n", guess, error);
        }
#endif
        
        guesses++;
    }
    
#ifdef DEBUG
    if (first_time) {
        printf("Val is %u, searchNum is %u. Guess is %d\n", val, searchNum, guess);
    }
#endif
    
    if (val < searchNum) {
        while (array[guess++] != searchNum) {}
    } else if (val > searchNum) {
        while (array[guess--] != searchNum) {}
    }

#ifdef DEBUG
    first_time = 0;
#endif
    
    return guess;
}

int diff(struct timeval start, struct timeval end) {
    return (end.tv_sec - start.tv_sec)*1000000 + (end.tv_usec - start.tv_usec);
}

int timeFunc(unsigned int *array, int size, int (*search)(unsigned int *,  int, unsigned int)) {
    struct timeval start, end;
    gettimeofday(&start, NULL);
    for (int i = 0; i < 1000000; i++) {
        int key_index = arc4random_uniform(size);
        int val = array[key_index];
        int result = search(array, size, val);
        if (abs(result-key_index) > 10) {
            printf("Search function %p got query for value %u at index %d wrong. Returned %d.\n", search, val, key_index, result);
            return -1;
        }
    }
    gettimeofday(&end, NULL);
    return diff(start, end);
}

#define ARRSIZE 100000000

int main() {
    unsigned int *array = generateArray(ARRSIZE);
        
    // printf("Took %f milliseconds to run linear search\n", (float)timeFunc(array, ARRSIZE, linearSearch)/1000);
    
    printf("Took %f milliseconds to run binary search\n", (float)timeFunc(array, ARRSIZE, binarySearch)/1000);
    
    printf("Took %f milliseconds to run interpolation search\n", (float)timeFunc(array, ARRSIZE, interpolationSearch)/1000);
    
    return 0;
}