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]，如果优化编译器可以证明访问之间的值不会改变任何内容（这可能需要在long * lArray声明中添加restrict;或者，您可以将元素加载到局部变量中并测试两次）。 无论哪种方式，如果每次迭代只需要一个数组查找，那么将索引从 mid 更改为 sizeArray - 1 - mid 每次迭代只会增加 2 个额外的减法（如果您在进入循环之前--sizeArray，则只需 1 个），我预计这不会像 n.m. 的方法那样增加常量。 当然，与任何事情一样，如果性能至关重要，请对其进行测试;如果不是，那么不要太担心节省微秒。

您还需要"反转"返回值：

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