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 double (substract_fn_t) (const void *restrict, const void *restrict);

static inline long double 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 double)(*(const int *restrict)a - *(const int *restrict)b);
}

static inline long double interpolate(const void *restrict val, const void *restrict data, size_t sz, size_t left, size_t right, substract_fn_t subtract) {
    return (long double)left + ((long double)(right - left) * subtract(val, (char *)data + (left * sz))) / subtract((const char *restrict)data + (right * sz), (char *)data + (left * sz));
}

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, substract_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>

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);
    }

    return 0;
}

#endif