I have an array of elements. The array is sorted by the ID of the elements, but the ID's are non-sequential e.g. there are gaps in the ID numbers.
I use binary search today to find a specific ID.
The ID is 3 bytes, which gives about 16 million possibilities. The number of ID's in a given array is much lower, maybe 10 000.
This is an embedded/plc platform, which means I can't have a 16MB lookup table, that takes too much memory. I've looked at bitsets an such, but I'm not sure if thats the right approach, or how to calculate an array offset from that.
I realize this may be a tough one given that I want to do the good old "speed for memory" trade-off, but I have very little memory, maybe 2MB or less to spare for this. But the hardware is fixed.
Edit: The elements of the array are fixed for a given application, no inserts or deletions of array elements.
How can I build/precompute a lookup table or similar to speed up locating an ID?
Thanks
I am assuming that the binary search is too slow. Since the table is fixed, there will be no additions or deletions during run-time, you can look at a "perfect hash" solution. Wiki has a really good artical explaiming this https://en.wikipedia.org/wiki/Perfect_hash_function
Basically, offline you need to run the table through a perfect hash generator, then during run time you run the ID through off-line generated formula to get the index of the item in the table.