c - 用于嵌入式系统的 C 中最快的数组查找算法？

Question

假设我有一个定义大小为 22 的 float 常量数组，如下所示:

array[0]= 0;
array[1]= 0.5;
array[2]= 0.7;
array[3]= 1.8;
...
...
array[21]= 4.2;

这个数组的值是单调的，也就是说，它们总是随着索引增加(array[0]<=array[1]<=array[2]<=....<=array[21]) .

我想要一个给定 float 的函数，它找到值紧接在输入 float 下方的数组的索引(因此，下一个索引的值紧接在输入 float 的上方)

例如，在前面的例子中，如果函数的输入值是 0.68，那么函数的输出应该是 1，因为 array[1]<= 0.68

现在，这很容易实现，但我正在处理嵌入式系统中时间非常关键的代码部分，我真的需要一个非常优化的算法，避免循环(避免开销).

我现在使用的最简单的方法就是用 if-elses 展开循环，仅此而已。

例子:

if(input >= array[size-1])
    return size-1;
else if(input>= array[size-2])
    return size-2;
else if(input >= array[size-3])
    return size-3;
...
...

但这里的问题是我有抖动，因为不同输入的路径花费的时间明显不同。

所以我的问题是:是否有最快且更具确定性(抖动更少)的方法来实现这一点？

谢谢。豪尔赫。

Answer 1

如果您使用二分查找，您将得到 O(log N):

size_t binaryFind(double x, double *array, size_t N) {
    size_t lower = 0;
    size_t upper = N;

    while (lower + 1 < upper) {
        mid = (lower + upper) / 2;
        if (x < array[mid]) {
            upper = mid;
        } else {
            lower = mid;
        }
    }
    if (array[lower] <= x) return lower;
    return (size_t)-1;
}

注意事项:

N 是数组中元素的数量。请注意，array[N] 在数组之外。数组必须按升序排序。

如果 x 小于 array[0]，则返回值为 (size_t)-1。这等同于失败。

返回值将是 N-1 是 x 大于 array[N-1]。