What is an elegant way to bin/map an integer in various categories in C?

Question

Assume we have an integer 'x' and 'n' possible values that 'x' can be mapped/binned to. What is an elegant way in C to have a function that returns the closest 'nth' value to x?

Pseudo code example;

int x = 40;
int res;
int bins[] = { 0, 20, 80, 200 }; /* Sorting is guaranteed */

res = int_bin(x, bins);
assert(res == 20); /* 40 is closer to 20 than 80 */

x = 150;

res = int_bin(x, bins);
assert(res == 200); /* 150 is closer to 200 than 80 */

By elegant I mean not just a bunch of if/else if/else statements.

Answer 1

If the list is sorted, then you can simply do a binary search for the value.

If the search does not find the value in the list, you will know at what index the value would have been located had it been in the list. Then, you can then compare the value against the element at that index and the element at the previous index (if the index isn't zero, obviously) and see which is closer.

Answer 2

Answering my own question here.

Since I'd like to reuse as much standard C functions as possible. I don't believe I can use bsearch() because that will give me no information as to the index of where the element should go if not found; I'd need to roll my own.

However, what about using qsort() on the bins[] array and give a comparison function that sorts based on how close the bin is to 'x' and then choosing the 0'th element as my answer?

Answer 3

Instead of storing the central value of each bin, store the boundary values around each bin. Use sentinel values at the beginning and end of the array to ensure that a search always finds an answer. In your example, replace { 0, 20, 80, 200 } with { INT_MIN, 10, 50, 140, INT_MAX }.

You can use a linear search if the real problem is as simple as your example. Otherwise, a binary search is the way to go.