Return to Question

#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

#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

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

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

#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 int64_t (*subtract_fn_t)(const void *restrict, const void *restrict);

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

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) {
    int64_t 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, 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);
}

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