A program to see the performance difference between linear search and binary search.

search_comparison.c

#include <stdio.h>
#include <time.h>

int linear_search(int ara[], int n, int key)
{
    for (int i = 0; i < n; i++) {
        if (ara[i] == key) {
            return i;
        }
    }

    return -1;
}

int binary_search(int ara[], int n, int key) 
{
    int left = 0, right = n - 1, mid;
    
    while (left <= right) {
        mid = (left + right) / 2;
        if (ara[mid] == key) {
            return mid;
        }
        if (key < ara[mid]) {
            right = mid - 1;
        }
        else { // key > ara[mid]
            left = mid + 1;
        }
    }

    return -1;
}

int main() 
{
    const int n = 200000;
    int ara[n];
    int i, key, result;

    clock_t start, end;
    double time_taken;

    // populate the array (numbers will be sorted!)
    for(i = 0; i < n; i++) {
        ara[i] = i;
    }

    printf("Testing Linear Search\n");
    start = clock();
    for (key = 0; key <= n; key++) {
        result = linear_search(ara, n, key);
    }
    end = clock();
    time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Done!\n");
    printf("linear_search took %.2lf to execute\n", time_taken);

    printf("Testing Binary Search\n");
    start = clock();
    for (key = 0; key <= n; key++) {
        result = binary_search(ara, n, key);
    }
    end = clock();
    time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Done!\n");
    printf("binary_search took %.2lf to execute\n", time_taken);

    return 0;
}