我正在实现有效的算法来搜索最后一次出现的(键或最接近的匹配(上限))。
到目前为止,我明白了。
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 应该返回索引 7
,但我的 fce 返回 4
请注意,我不想线性迭代到最后一个匹配索引。
记住,我有一个解决方案,我更改参数fce(添加开始,结束索引)并使用fce从找到的上界到数组末尾进行另一个二分搜索(仅当我没有找到完全匹配时,last_occur =-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;
关于c - 二分查找与最后一次出现的最接近的匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27125391/