javascript - 寻找魔术索引的二进制搜索

Question

我正在练习二进制搜索，但在尝试实现二进制搜索以查找数组中的“魔术索引”时遇到了困难。魔术索引是 A[i] == i。

我在 Java using recursion 中找到了一些实现，但我试图避免以递归方式执行此操作，因为递归很昂贵(我想看看二分查找在这里是否合适)。

这是我的代码:

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

您的第二个数组未排序并且 binary search仅适用于排序数组。