用于查找魔术指数的二进制搜索

Question

我正在练习二叉搜索，在尝试实现它以查找数组中的"魔术索引"时，我遇到了一堵墙。魔法指数A[i] == i .

我在 Java 中发现了一些使用递归的实现，但我试图避免递归这样做，因为递归很昂贵(我想看看二叉搜索在这里是否合适(。

这是我的代码：

function magicIndex(arr) {
  var result = arr, mid;
  while (result.length > 1) {
    mid = Math.floor(result.length / 2);
    if (result[mid] === mid) {
      return arr.indexOf(result[mid]);
    } else if (mid > result[mid]) {
      result = result.slice(mid+1, result.length);
    } else {
      result = result.slice(0, mid);
    }
  }
  return arr.indexOf(result.pop());
}

问题在于，该算法在某些测试运行中错误地将数组切到错误的一侧。

例如，[-10, -3, 0, 2, 4, 8]返回4，但[-10, 1, 0, 2, 5, 8]也返回4。

Answer 1

您的第二个数组未排序，二分搜索仅适用于排序数组。

Answer 2

既然你在练习，我认为你自己编码对你有好处，但我会给你一个指导。

使用此算法(请注意，输入数组应该已经排序，否则实现排序方法(：

  int arr[n];
  K ← 1; //search key
  l ← 0; r ← n - 1;
  while l ≤ r do
      m ← floor((l + r)/2)
      if K = arr[m]
          return m
      else if K < arr[m]
          r ← m − 1
      else
          l ← m + 1
  return −1

这将输出搜索键的索引，如果未找到键，则为 -1。