二进制搜索给了我一个段错误

Question

我正在尝试运行二进制搜索的这种实现。我不知道为什么，但它一直给我segfault错误。我认为问题可能是我传递数组的方式或者递归调用有问题。

#include <stdio.h>

int hasBinarySearch(int *array, int low, int high, int element)
{

    int mid = (low + (high-low)) / 2;

  if (high>=low)
  {

    if (array[mid] == element)
    {
      return mid;
    }
    else if(array[mid]<element)
    {
        return hasBinarySearch(array, low, mid-1, element);
    }
    else
    {
      return hasBinarySearch(array, mid+1, high, element);
    }
  }

  return 0;
}



int main(void)
{
  int array[10] = {1,2,3,4,5,6,6,6,7,8};
  hasBinarySearch(array, 0, 9, 2);

  return 0;
}

Answer 1

我认为你对二元搜索有一些误解。阅读一些文章或书籍。

正如@Claies评论的那样，计算中间索引是错误的。它应该是低+（高 - 低）/ 2.只要想想数学中两点的内部划分。

此外，您必须修复递归调用的参数，如下面的代码。

#include <stdio.h>

int hasBinarySearch(int *array, int low, int high, int element)
{

    int mid = low + (high - low) / 2; // changed
    printf("%d %d\n", high, low);
    if (high >= low)
    {
        if (array[mid] == element)
        {
            return mid;
        }
        else if (array[mid] < element)
        {
            return hasBinarySearch(array, mid + 1, high, element); // changed
        }
        else
        {
            return hasBinarySearch(array, low, mid - 1, element); // changed
        }
    }
    return 0;
}

int main(void)
{
    int array[10] = { 1,2,3,4,5,6,6,6,7,8 };
    hasBinarySearch(array, 0, 9, 2);
    return 0;
}

Answer 2

int mid = (low + (high-low)) / 2; // wrong formula

@paganinist的好答案指出了OP的搜索方法和修复方法的缺陷。

---

然而要深入挖掘。

尽管一些编译器可能能够“解除代码”（Example），但这里不需要递归。一个简单的循环就足够了。

在极端情况下，阵列大小可接近最大值或超过int的范围。 对于高int范围内的尺寸，以下是更好的。 @Jonathan Leffler

// int mid = (low + high)/2;  // could overflow
int mid = low + (high-low)/2; // better, will not overflow when low >= 0

要适应所有数组大小，请在size_t上使用int。这也处理大小，包括INT_MAX附近和以上的大小。

---

返回匹配元素地址的候选解决方案，如果未找到，则返回NULL。

#include <stdlib.h>
#include <stdio.h>

int *BinarySearch_int(const int *array, size_t count, int key) {
  while (count > 0) {
    size_t mid = count / 2;
    if (key > array[mid]) {
      array += mid + 1;
      count -= mid + 1;
    } else if (key < array[mid]) {
      count = mid;
    } else {
      return (int *) &array[mid];
    }
  }
  return NULL;
}

测试代码

bool BinarySearch_int_test(const int *array, size_t count, int key, bool target){
  int *p = BinarySearch_int(array, count, key);
  bool success = (p != NULL) == target && (p == NULL || *p == key);
  printf("f(Array:%p count:%zu, key:%2d) --> ptr:%p value:%2d success:%d\n",
      (void*) array, count, key, (void*) p, p ? *p : 0, success);
  return success;
}

int main(void) {
  int array[] = {10, 20, 30, 40, 50, 60};
  size_t n = sizeof array / sizeof array[0];
  for (size_t i = 0; i < n; i++) {
    BinarySearch_int_test(array, n, array[i], 1);
  }
  BinarySearch_int_test(array, n, 0, 0);
  for (size_t i = 0; i < n; i++) {
    BinarySearch_int_test(array, n, array[i] + 1, 0);
  }
}

产量

f(Array:0xffffcb90 count:6, key:10) --> ptr:0xffffcb90 value:10 success:1
...
f(Array:0xffffcb90 count:6, key:60) --> ptr:0xffffcba4 value:60 success:1
f(Array:0xffffcb90 count:6, key: 0) --> ptr:0x0 value: 0 success:1
...
f(Array:0xffffcb90 count:6, key:61) --> ptr:0x0 value: 0 success:1

Answer 3

mid的计算简化为high / 2，因为你已经添加然后再次减去下限。看起来你的意思是将一半的差异加到下限，但是分裂发生得太迟了。它应该是low + (high-low) / 2。 （这比(low + high) / 2复杂一点，但避免了其他地方提到的整数数学问题。）

我认为当high低于low并且变得太小而你从阵列的开头掉下来时会发生段错误。

@paganinist对于上下案件是倒退是正确的。