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

int binarySearch(int arr[], int size, int val) {
    int lo = 0;
    int hi = size - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (val < arr[mid]) {
            printf("It's small than %d, let's keep looking!\n", arr[mid]);
            hi = mid - 1;
        } 
        else if (val > arr[mid]) {
            printf("It's bigger than %d, let's keep looking!\n", arr[mid]);
            lo = mid + 1;
        } 
        else {
            printf("Found it! It's in position %d\n", mid);
            return mid;
        }
    }
    return -1;
}

int main(void) {
    const size_t arr_size = 10;
    int *my_nums = malloc(arr_size * sizeof(int));
    for (size_t i = 0; i < arr_size; i++) {
        my_nums[i] = (int)i;
    }

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    int result = binarySearch(my_nums, arr_size, (int)(arr_size - 1));

    clock_gettime(CLOCK_MONOTONIC, &end);

    double seconds =
        (end.tv_sec - start.tv_sec) +
        (end.tv_nsec - start.tv_nsec) / 1000000000;

    printf("Result: %d\n", result);
    printf("Time taken for %zu items: %.3f seconds\n",
           arr_size, seconds);

    free(my_nums);
    return 0;
}