While Loop 永远运行并且在二进制搜索中不会 return

Question

正在尝试为反向数组输入实现二进制算法。当我执行测试用例时 - 5 4 3 2 1 它向我显示了一个空白屏幕，即 while 循环运行 infinitely.Trying 以调试它一段时间但无法弄清楚我哪里出错了。

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

int findright(int arr[], int key, int low, int high);

void main() {
  int n, i, arr[200], key;
  scanf("%d %d\n", &n, &key);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  int a = findright(arr, key, 1, n - 1);
  printf("%d", a);
}

int findright(int arr[], int key, int low, int high) {

  int mid = (low + high) / 2;
  while (low <= high) {
    if (arr[mid] == key) {
      return mid;
    } else if (arr[mid] > key) {
      findright(arr, key, mid + 1, high);
    } else {
      findright(arr, key, low, mid - 1);
    }
  }
  return -1;
}

Answer 1

在您的循环 while (low <= high) { ... 中，low 和 high 的值没有改变；因此，一旦进入循环，就永远不会 return.

当你使用递归时，你将不需要循环：

int findright(int arr[], int key, int low, int high) {

  if (low > high) { // anchor stopping recursion
    return -1;  // indicate that key was not found...
  }

  int mid = (low + high) / 2;
  if (arr[mid] == key) {
      return mid;
  } else if (arr[mid] > key) {
      return findright(arr, key, mid + 1, high);
  } else {
      return findright(arr, key, low, mid - 1);
  }
}

Demo.

进一步注意，如 MFisherKDX 所述 - "you also have an off-by-one error in your main. You are passing 1 as low and therefore will never check the 0-th element"。

Answer 2

我看到的问题：

需要将 while 更改为 if。
递归调用前面需要有return。
您正在使用 low 的错误值调用函数。

int findright(int arr[], int key, int low, int high) 
{
    int mid = (low + high) / 2;
    if (arr[mid] == key)
    {
        return mid;
    }

    // Terminate recursion when the item is not found.
    if ( low == high )
    {
        return -1;
    }

    if (arr[mid] > key)
    {
        return findright(arr, key, mid + 1, high);
    }

    else
    {
        return findright(arr, key, low, mid - 1);
    }
}

来电

int a = findright(arr, key, 1, n - 1);

需要改为：

int a = findright(arr, key, 0, n - 1);

需要注意的一件事是标准库函数使用迭代器，因此 end 是最后一个有效迭代器之后的一个。当您使用索引实现函数时，类似的值将是大于 1 的最高有效索引的索引。您可以将该函数称为：

int a = findright(arr, key, 0, n);

并以稍微不同的方式实现函数：

int findright(int arr[], int key, int low, int high) 
{
    // Terminate recursion when the item is not found.
    if ( low == high )
    {
        return -1;
    }

    int mid = (low + high) / 2;
    if (arr[mid] == key)
    {
        return mid;
    }

    if (arr[mid] > key)
    {
        return findright(arr, key, mid + 1, high);
    }

    else
    {
        return findright(arr, key, low, mid);
    }
}

While Loop 永远运行并且在二进制搜索中不会 return

While Loop runs forever and does not return in binary serach

c

binary-search