二进制搜索与最后一次匹配的最接近的匹配

我正在实现有效的算法来搜索（密钥或最近的匹配（上限））的最后一次出现。二进制搜索与最后一次匹配的最接近的匹配

到目前为止，我得到了这一点。

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）。

我想问问有没有更好/更简洁的方案来实现它？

来源

2014-11-25 Rob

不知道为什么它应该返回7.它要求找到钥匙，或最近比赛的最后一次出现，因此，如果关键不在列表中（这是你的例子） - 返回4应该没问题，因为我理解任务描述。 – amit 2014-11-25 11:36:40

@amit编辑了这个问题。现在应该更清楚了 – Rob 2014-11-25 11:41:49

你打开一个{在你的while指令之后，你永远不会关闭它。 – 2014-11-25 11:44:56

纳米的2-搜索方法将工作，并保持最佳的时间复杂度，但它可能是由约2至增加常数因子，或约1.5，如果你开始从第一次搜索结束，其中第二搜索。

相反，如果你采取的发现lnumber的第一实例（或者，如果它不存在，下限），并改变它，这样的算法逻辑“反转”的“普通”的二进制搜索阵列，通过改变每一个数组访问lArray[x]lArray[sizeArray - 1 - x]到（对于任何表达x），并且还通过改变> lnumber测试< lnumber“反向”的排序，则需要只有一个单一的二进制搜索。唯一的数组访问这个算法实际执行两种查找到lArray[mid]，其中优化的编译器很可能只计算一次，如果能证明，没有什么会改变访问之间的值（这可能需要增加restrict到long * lArray声明;或者，您可以将该元素加载到局部变量中，然后测试两次）。无论哪种方式，如果只需要每次迭代一个数组查找，然后改变从mid到sizeArray - 1 - mid指数将增加每次迭代只需2个额外的减法（或只有1，如果你--sizeArray进入循环前），我预计不会增加几乎和纳米的方法一样。当然，就像任何事情一样，如果性能很关键，那就测试一下;如果不是，那么不要太在意节省微秒。

您还需要“反向”的返回值过：

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

来源

2014-11-25 14:26:05

二进制搜索与最后一次匹配的最接近的匹配

回答

相关问题