How can I check in which array a value is in C?

Question

Let's say I have three arrays:

const uint8_t arr_1[] = {1, 4, 53 , 209};
const uint8_t arr_2[] = {54, 56, 90, 100};
const uint8_t arr_3[] = {6, 7, 8, 9, 10};

How can I efficiently check if a given value uint8_t val is in one of the arrays and if it is, in which one. One way is to loop through all the arrays until the value is found, but that is not very efficient. The solution needs to scale to many more arrays. The values in each array can be sorted if necessary.

Answer 1

I'm going to summarize my comments on your post in an answer. Hoping it would be of use to someone.

If you hold for each array a pointer and its range of values, say like this:

struct arr_meta_data {
  const uint8_t *p_arr;
  uint8_t min;
  uint8_t max;
};

Then you can sort the array of struct arr_meta_data based on the partial order that the ranges define.

Looking up a value is then a two step process

1. Binary search in the array of struct arr_meta_data to find the first array where the value can be located. O(log M) where M is how many arrays you have.

2. Move forward and binary search in each of the arrays where the value is in range. Once you reach an array where the value is less than the minimum, you can stop and return that the value wasn't found.

Answer 2

Inspired from @StoryTeller, I attempted to use his approach.

I constructed the code only considering the 3 arrays given:

const uint8_t arr_1[] = {1, 4, 53 , 209};
const uint8_t arr_2[] = {54, 56, 90, 100};
const uint8_t arr_3[] = {6, 7, 8, 9, 10};

as I did not know how the data is given. The idea is correct, and I assumed the arrays are always sorted. If this is not the case in the future, then you can just sort the arrays using qsort beforehand, which has O(nlogn) running time on average.

In the following code, I used:

1. The builtin bsearch function provided by stdlib.h, to save trouble writing your own. Using this binary search tool still allows O(logn) search time, which is much better than O(n) time consumed from linear search.

2. Array of structures setup, to gather specific information about each array, such as checking the [min, max] range, and skipping arrays that don't fall in the same range as the search key value

   Setup:

   typedef struct {
       const uint8_t *p_arr;
       uint8_t currsize; * size of each array */
       uint8_t max; /* Ranges */
       uint8_t min;
   } array_t;
   
   typedef struct {
       array_t *A; /* pointer to array information */
       uint8_t numarrays; /* just a buddy vairable to keep track of n arrays */
   } data_t;
   

3. Necessary calls to malloc and free, to allocate and deallocate space for pointer variables on the heap.

Here is what I came up with:

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

#define INITSIZE 3

typedef struct {
    const uint8_t *p_arr;
    uint8_t currsize;
    uint8_t max;
    uint8_t min;
} array_t;

typedef struct {
    array_t *A;
    uint8_t numarrays;
} data_t;

data_t *initialize_meta_data(void);
int check_arrays(const uint8_t arr[], const size_t n, uint8_t *key);
void set_arrays(data_t *data, const uint8_t arr[], const size_t n, int index);
void search_arrays(data_t *data, uint8_t key);
int cmpfunc(const void *a, const void *b);

int
main(void) {
    const uint8_t arr_1[] = {1, 4, 53 , 209};
    const uint8_t arr_2[] = {54, 56, 90, 100};
    const uint8_t arr_3[] = {6, 7, 8, 9, 10};

    const size_t size1 = sizeof(arr_1)/sizeof(*arr_1);
    const size_t size2 = sizeof(arr_2)/sizeof(*arr_2);
    const size_t size3 = sizeof(arr_3)/sizeof(*arr_3);

    data_t *data = initialize_meta_data();

    data->A = malloc(data->numarrays * sizeof(*(data->A)));

    set_arrays(data, arr_1, size1, 0);
    set_arrays(data, arr_2, size2, 1);
    set_arrays(data, arr_3, size3, 2);

    /* Number to search for */
    uint8_t key = 10;

    search_arrays(data, key);

    free(data->A);
    free(data);

    return 0;
}

void
search_arrays(data_t *data, uint8_t key) {
    int i;

    for (i = 0; i < data->numarrays; i++) {
        if ((key <= data->A[i].max) && (key >= data->A[i].min)) {
            if (check_arrays(data->A[i].p_arr, data->A[i].currsize, &key)) {
                printf("%d found in array number: %d\n", key, i+1);
            }
        } else {
            printf("array number: %d skipped\n", i+1);
        }
    }
}

void
set_arrays(data_t *data, const uint8_t arr[], const size_t n, int index) {
    data->A[index].p_arr = arr;
    data->A[index].currsize = n;
    data->A[index].max = data->A[index].p_arr[data->A[index].currsize-1];
    data->A[index].min = data->A[index].p_arr[0];
}

data_t
*initialize_meta_data(void) {
    data_t *data = malloc(sizeof(*data));
    data->A = NULL;
    data->numarrays = INITSIZE;
    return data;
}

int
check_arrays(const uint8_t arr[], const size_t n, uint8_t *key) {
    uint8_t *item;

    item = bsearch(key, arr, n, sizeof(*arr), cmpfunc);

    if (item != NULL) {
        return 1;
    }

    return 0;
}

int
cmpfunc(const void *a, const void *b) {
    return (*(uint8_t*)a > *(uint8_t*)b) - (*(uint8_t*)a < *(uint8_t*)b);
}

Overall, this code can be heavily optimized, and you will probably use a very different approach for your project, but the idea will be similar.

I hope it somewhat helps :)

Answer 3

#include <stdio.h>
#include <stdint.h>

const uint8_t arr_1[] = {1, 4, 53 , 209};
const uint8_t arr_2[] = {54, 56, 90, 100};
const uint8_t arr_3[] = {6, 7, 8, 9, 10};

uint8_t lookup[256] = {0,};

void add_one(const uint8_t *arr, unsigned count, unsigned num)
{
unsigned uu, val;

for (uu=0; uu < count; uu++) {
        val = arr[uu];
        if (lookup[val]) fprintf(stderr
                , "Add_one(num = %u): OMG!1111! value=%u also present in array_%u\n"
                , num, val, (unsigned) lookup[val] );
        lookup[val] = num;
        }
}

void do_init(void)
{
add_one(arr_1, 4, 1);
add_one(arr_2, 4, 2);
add_one(arr_3, 6, 3);
}

int main(void)
{
unsigned idx,val;

do_init();

for (val = 0; val < 256; val++) {
        idx = lookup[val];
        if (!idx) continue;
        printf("Value %u is in arr_%u\n", val, idx);
        }

return 0;
}

Answer 4

Since it's uint8_t you could use a bitarray. There is no sort no loop. This code is not tested, but the idea can be seen.

uint arrEle(uint8_t val) { return val/32; }
uint arrBit(uint8_t val) { return 1<<(val%32); }

void setBit(uint32_t *arr, uint8_t val) {
    arr[arrEle(val)]|=arrBit(val);
}
uint testBit(uint32_t *arr, uint8_t val) {
    return (arr[arrEle(val)]&arrBit(val)) ? 1:0;
}
void clrBit(uint32_t *arr, uint8_t val) {
    arr[arrEle(val)]&=~arrBit(val);
}

// sorry not static initialize
const uint32_t arr_all[4][8] = {0};
const uint32_t arr_1[][8] = arr_all[0];
const uint32_t arr_2[][8] = arr_all[1];

setBit(arr_1, 1);
setBit(arr_1, 4);
setBit(arr_1, 53);
setBit(arr_1, 209);

Now your test is as simple as:

for(i=0;i<sizeof(arr_all)/sizeof(*arr_all);i++) 
  if(testBit(arr_all[i], val)) return i;  // return the array number 0..3