0

假设我们有一个整数“x”和“n”个可能的值，“x”可以映射/合并到。什么是 C 中的一种优雅方式，可以让函数返回最接近 x 的“第 n 个”值？

伪代码示例；

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 */

优雅我的意思不仅仅是一堆 if/else if/else 语句。

4

3 回答 3

5

如果列表已排序，那么您可以简单地对该值进行二进制搜索。

如果搜索未在列表中找到该值，您将知道如果该值在列表中，该值将位于哪个索引处。然后，您可以将该值与该索引处的元素和前一个索引处的元素进行比较（如果索引不为零，显然）并查看哪个更接近。

于 2010-06-22T18:52:24.660 回答
1

不是存储每个 bin 的中心值，而是存储每个 bin 周围的边界值。在数组的开头和结尾使用标记值，以确保搜索总能找到答案。在您的示例中，替换{ 0, 20, 80, 200 }为{ INT_MIN, 10, 50, 140, INT_MAX }.

如果真正的问题与您的示例一样简单，您可以使用线性搜索。否则，二分搜索是要走的路。

于 2010-06-22T21:43:14.813 回答
0

在这里回答我自己的问题。

因为我想尽可能多地重用标准 C 函数。我不相信我可以使用 bsearch() 因为这不会给我任何关于如果找不到元素应该去哪里的索引的信息；我需要自己动手。

但是，如何qsort()在 bins[] 数组上使用并给出一个比较函数，该函数根据 bin 与“x”的接近程度进行排序，然后选择第 0 个元素作为我的答案？

于 2010-06-22T19:04:54.053 回答