嵌入式系统C中最快的阵列查找算法？

Question

假设我有一个定义大小为22的常量浮点数,如下所示:

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]).

我想要一个给定一个浮点数的函数,它找到数值的索引,其值正好在输入浮点数之下(因此,下一个索引的值紧接在上面)

例如,在前一种情况下,如果函数的输入值为0.68,则函数的输出应为1,因为数组[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]它位于数组之外.数组必须按升序排序.

返回值将是(size_t)-1,如果x小于array[0].这是失败的等价物.

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