尝试为反向数组输入实现二进制算法。
当我为测试用例执行时-
5 4 3 2 1它给我显示了一个空白的屏幕,即while循环无限运行。现在试图调试它一段时间,但无法找出哪里出错了。

#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;
}

最佳答案

在循环while (low <= high) { ...中,lowhigh的值不会更改;因此,如果一次输入循环,它将永远不会返回。
使用递归时,不需要循环:

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所提到的,“您的main中也有一个off-by-one错误。您将1作为低位传递,因此永远不会检查第0个元素”。

关于c - 虽然Loop会永远运行,并且不会在二进制搜索中返回,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49740573/

10-11 23:12
查看更多