0

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

到目前为止，我得到了这个。

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}，关键是6 Fce 应该返回 index 7，但我的 fce 返回4

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

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

我想问是否有更好/更清洁的解决方案来实施它？

4

1 回答 1

0

nm 的 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 个），我预计这不会增加常数就像nm的方法一样。当然，与任何事情一样，如果性能很关键，那么就对其进行测试；如果不是，那么不要太担心节省微秒。

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

return last_occur!=-1?last_occur:sizeArray - 1 - mid;
于 2014-11-25T14:26:05.283 回答