c - C 语言的二分查找算法

Question

我正在尝试用 C 语言编写一个二分查找函数，但遇到了一些问题。首先，在找到中点值之后，该函数甚至没有进入任何 if 循环。

函数是这样的:

   int binarychopsearch(int i, int *array, int min, int N) {

min = 0;
int max = N - 1;
printf("Min = %d, Max = %d\n", min, max);
printf("i = %d\n", i);



        int mid = (min + max)/2;
        //printf("midpoint = %d\n", mid);
        printf("array[%d] = %d\n", mid, array[mid]);
  if (i < array[mid]) {
        printf("in this loop\n");
        printf("i = %d, array[mid] = %d\n", i, array[mid]);
        // key is in lower subset
        return binarychopsearch(i, array, min, mid - 1);
        }


  else if (i > array[mid]) { 
      printf("in the greater than loop\n");
      printf("i = %d, array[mid] = %d\n", i, array[mid]);
      return binarychopsearch(i, array, mid + 1, max);
      }

  else 

  //if (i = array[mid]) {

        return mid;
}

我不包括输入值的主要来源，因为我认为问题出在这个函数中。它正在编译并运行，但没有进入循环，因此找不到“i”值的位置。我对此很困惑，因为我看不出哪里出了问题。

非常感谢任何帮助!

谢谢

Answer 1

如果i大于(或等于)array[mid]，则您无条件从函数返回。相反，您应该检查下一个条件，如果该条件也为假，您就知道您已经找到了您正在寻找的值。

所以它应该看起来像

if (i < array[mid])
{
    ...
}
else if (i > array[mid])
{
    ...
}
else
    return mid;

<小时/>

您的代码还存在其他问题。

假设您有以下数组

int array[] = { 1, 2, 3, 4, 5 };

您正在寻找值5。

调用将如下所示:

| Call# | min | N | max | mid | array[mid] ||   1   |  0  | 5 |  4  |  2  |    3       ||   2   |  3  | 4 |  3  |  3  |    4       ||   3   |  4  | 3 |  2  |  2  |    3       ||   4   |  3  | 2 |  1  |  2  |    3       ||   5   |  3  | 1 |  0  |  1  |    2       ||   6   |  2  | 0 | -1  |  1  |    2       |...

It's quite clear that this will not end well. In fact, you will soon end up with negative index, and that leaves you in the territory of undefined behavior.

I suggest you create your own table like this, on paper, when trying to fix your algorithm, for both cases of recursion.

If you don't call the recursive function with max but with N instead, i.e.

return binarychopsearch(i, array, mid + 1, N);

然后您将收到以下电话

| Call# | min | N | max | mid | array[mid] ||   1   |  0  | 5 |  4  |  2  |    3       ||   2   |  3  | 5 |  4  |  3  |    4       ||   3   |  4  | 5 |  4  |  4  |    5       |

So the third call found the number, and returns the index 4.

You should also change the first call:

return binarychopsearch(i, array, min, mid);