c - 二分查找与最后一次出现的最接近的匹配

Question

我正在实现有效的算法来搜索最后一次出现的(键或最接近的匹配(上限))。

到目前为止，我明白了。

long bin_search_closest_match_last_occurance ( long  * lArray, long sizeArray, long lnumber)
{
    long left, right, mid, last_occur;

    left = 0;
    right = sizeArray - 1;
    last_occur = -1;

    while ( left <= right )
    {
        mid = ( left + right ) / 2;

        if ( lArray[mid] == lnumber  )
        {
            last_occur = mid;
            left = mid +1;
        }

        if ( lArray[mid] > lnumber ) 
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return last_occur!=-1?last_occur:mid;
}

让我们有一个数组{0,0,1,5,9,9,9,9}，键是6Fce 应该返回索引 7，但我的 fce 返回 4

请注意，我不想线性迭代到最后一个匹配索引。

记住，我有一个解决方案，我更改参数fce(添加开始，结束索引)并使用fce从找到的上界到数组末尾进行另一个二分搜索(仅当我没有找到完全匹配时，last_occur =-1)。

我想问是否有更好/更干净的解决方案来实现它？

Answer 1

n.m. 的 2 次搜索方法会起作用，并且它会保持最佳时间复杂度，但它可能会将常数因子增加大约 2，或者如果您从第一次搜索结束的地方开始第二次搜索，则可能会增加大约 1.5。

如果您采用“普通”二分搜索来查找 lnumber 的第一个实例(或者，如果不存在，则更改下限)，并更改它，以便算法通过更改每个数组访问来逻辑“反转”数组 lArray[x]至lArray[sizeArray - 1 - x] (对于任何表达式 x )，也可以通过更改 > lnumber 来“反转”顺序测试< lnumber ，那么只需要一次二分查找。该算法实际执行的唯一数组访问是对 lArray[mid] 的两次查找。 ，如果优化编译器能够证明不会改变访问之间的值，则很可能只计算一次(这可能需要将 restrict 添加到 long * lArray 的声明中；或者，您可以只加载该元素到局部变量并测试它两次)。无论哪种方式，如果每次迭代只需要一次数组查找，则将索引从 mid 更改为至sizeArray - 1 - mid每次迭代只会添加 2 个额外的减法(或者如果您在进入循环之前 --sizeArray 则仅添加 1 个减法)，我预计这不会像 n.m. 的方法那样增加常数。当然，与任何事情一样，如果性能至关重要，那么就对其进行测试；如果不是，那么不必太担心节省微秒。

您还需要“反转”返回值:

return last_occur!=-1?last_occur:sizeArray - 1 - mid;