Performs interpolation binary search over an array. If value found returns found and index else returns not found and insertion index

Question

Performs interpolation binary search over an array sorted in ascending order. If value found returns found and index else returns not found, the insertion index is returned. Assumptions :

1. data is sorted in ascending order and all the values in data are unique
2. left >=0 and right <= data.size - 1 and left < right during input

File array_search.h

#pragma once
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

typedef int (*cmp_fn_t)(const void *restrict, const void *restrict);

static inline int compare_int(const void *restrict a, const void *restrict b) { //compare_int is provided as an example
    const int arg1 = *(const int*)a;
    const int arg2 = *(const int*)b;
    return (arg1 > arg2) - (arg1 < arg2);
}

typedef long long (*subtract_fn_t)(const void *restrict, const void *restrict);

static inline long long subtract_int(const void *restrict a, const void *restrict b) { //subtract_int is provided as an example // a > b if positive answer is expected -> a - b
    return (long long)((*(const int *restrict)a - *(const int *restrict)b));
}

static inline size_t interpolate(const void *restrict val, const void *restrict data, size_t sz, size_t left, size_t right, subtract_fn_t subtract) {
    long long fraction = subtract(val, (char *)data + (left * sz)) / subtract((const char *restrict)data + (right * sz), (char *)data + (left * sz));
    return (fraction >= 0) ? left + ((right - left) * (size_t)fraction) : (left - ((right -left) * (size_t)(-fraction)));
}

static inline void update_ib_search_bounds(const void *restrict val, const void *restrict data, size_t sz, size_t *interpolation, size_t *left, size_t *right, cmp_fn_t cmp) {
    const char *restrict dataBytes = (const char *restrict)data;
    size_t mid;
    if(cmp(val, dataBytes + (*interpolation) * sz) > 0) {
        (*interpolation)++;
        if(cmp(val, dataBytes + (*interpolation) * sz) <= 0) {
            *left = *right = *interpolation;
            return;
        }
        mid = (*interpolation + *right) / 2;
        *left = (cmp(val, dataBytes + (mid * sz)) <= 0) ? ((*right = mid), (*interpolation + 1)) : (mid + 1);        
    } else {
        size_t lookIdx = *interpolation - 1;
        if(*interpolation == *left || cmp(val, dataBytes + (lookIdx) * sz) > 0) {
            *left = *right = *interpolation;
            return;
        }
        mid = (*interpolation + *left) / 2;
        *right = (cmp(val, dataBytes + (mid * sz)) >= 0) ? ((*left = mid), lookIdx) : (mid - 1);
    }
}

static inline bool ibs_valIsInArray(const void *restrict val, const void *restrict data, size_t sz, size_t left, size_t data_len, size_t *idx, subtract_fn_t subtract, cmp_fn_t cmp) {
    if(data_len == 0 || cmp(val, (char *)data + (left * sz)) < 0) {
        *idx = left;
        return false;
    }
    size_t right = data_len - 1;
    if(cmp(val, (char *)data + (right * sz)) > 0) {
        *idx = data_len;
        return false;
    }
    while(left < right) {
        *idx = interpolate(val, data, sz, left, right, subtract);
        update_ib_search_bounds(val, data, sz, idx, &left, &right, cmp);
    }
    return cmp(val, (char *)data + (left * sz)) == 0;
}

static inline bool sq_valIsInArray(const void *restrict val, const void *restrict data, size_t sz, size_t left, size_t data_len, size_t *idx, cmp_fn_t cmp) {
    *idx = left;
    while (*idx < data_len && cmp(val, (char *)data + ((*idx) * sz)) > 0) {
        (*idx)++;
    }
    return (*idx < data_len) && (cmp(val, (char *)data + ((*idx) * sz)) == 0);
}

File test.c

#define TEST_1


#ifdef TEST_1
#include "array_search.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    
    int array1[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55};
    int array2[] = {1,10,15,30,400,401,402,600,620,640,650,700,701,702,705,2000,2005,3000,3200,3400,3500,3600,6000,6200,6500,6700,6800,6801,6803,8000,9001,9010,9100,9300,9500,9601,9602,9802,9900};
    int array3[] = {343, 1540, 1562, 2135, 2275, 2559, 3780, 4440, 4946, 6110, 6200, 7040, 7290, 7541, 7881, 9269};
    printf(
        "Arrays available:\n"
        "1)array1[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55}\n"
        "2)array2[] = {1,10,15,30,400,401,402,600,620,640,650,700,701,702,705,2000,2005,3000,3200,3400,3500,3600,6000,6200,6500,6700,6800,6801,6803,8000,9001,9010,9100,9300,9500,9601,9602,9802,9900}\n"
        "3)array3[] = {343, 1540, 1562, 2135, 2275, 2559, 3780, 4440, 4946, 6110, 6200, 7040, 7290, 7541, 7881, 9269};\n"
    );
    
    int number;
    clock_t start, end;
    double cpu_time_used;
    size_t array1_len = sizeof(array1) / sizeof(array1[0]);
    size_t array2_len = sizeof(array2) / sizeof(array2[0]);
    size_t array3_len = sizeof(array3) / sizeof(array3[0]);
    size_t idx;
    while(1) {
        printf("Enter array number:");
        scanf("%d", &number);
        int *p;
        size_t len;
        switch (number)
        {
        case 1:
            p = array1;
            len = array1_len;
            break;
        case 2:
            p = array2;
            len = array2_len;
            break;
        case 3:
            p = array3;
            len = array3_len;
            break;
        default:
            p = NULL;
            len = 0;
            exit(0);
            break;
        }
        printf("Enter a key to find in array %d: ", number);
        scanf("%d", &number);
        printf("You entered: %d\n", number);
        start = clock();
        bool b = ibs_valIsInArray(&number, p, sizeof(int), 0, len, &idx, subtract_int, compare_int);
        end = clock();
        if(b) {
            printf("Found at idx: ");
        } else {
            printf("Not found. idx is at :");
        }
        printf("%zu\n", idx);        
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("Time taken for IBS in array: %f seconds\n", cpu_time_used);
        start = clock();
        b = sq_valIsInArray(&number, p, sizeof(int), 0, len, &idx, compare_int);
        end = clock();
        if(b) {
            printf("Found at idx: ");
        } else {
            printf("Not found. idx is at :");
        }
        printf("%zu\n", idx);        
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("Time taken for SQ in array: %f seconds\n", cpu_time_used);
    }
    return 0;
}

#endif