C++ 二进制搜索，如 lower_bound

Question

我的二进制搜索确实有问题，应该有点像 lower_bound。这让我在 5th 运行中出现段错误。谁能看出问题？谢谢

int BinarySearch ( const char * a, int firstindex , int lastindex){
    if (m_len == 0) return 0; //number of items in searched array
    if ( firstindex == lastindex ) return lastindex;
    int tmp = lastindex - firstindex;
    int pos = tmp/2;
    if ( tmp % 2 != 0 ) ++pos;
    if (strcmp(a,Arr[pos]) < 0) return BinarySearch(a,firstindex,pos-1);
    if (strcmp(a,name) > 0) return BinarySearch(a,pos+1,lastindex);
    return pos;
}

Answer 1

int tmp = lastindex - firstindex;

应该是：

int tmp = lastindex + firstindex;

那是因为你正在寻找索引 x 和 y 的中间值，即 (x+y)/2。

您的代码的行为应该是不可预测的，可能会循环并导致分段错误。

Answer 2

x 和 y 的中点是 x + (y - x)/2，所以你想要

int pos = firstIndex + tmp/2;

使用稍微复杂的表达式而不是明显的 (x + y)/2 消除了一个非常常见的溢出错误。

C++ 二进制搜索，如 lower_bound

C++ Binary search like lower_bound

c++

search

binary