javascript - 如果使用二分搜索（递归）找到元素，如何获取元素的索引

Question

function getMiddle({right,left}) {
  return Math.floor((left + right) / 2);
}

function RecursivelyBinarySearch(arr, search) {
  let left = 0;
  let right = arr.length - 1;
  let middle = getMiddle({left,right});
  if (right >= left) {
    if (arr[middle] === search) {
      return middle;
    } else if (arr[middle] < search) {
      return RecursivelyBinarySearch(arr.slice(middle + 1, arr.length), search);
    } else {
      return RecursivelyBinarySearch(arr.slice(0, middle - 1), search)
    }
  }
  return -1;
}

let result = RecursivelyBinarySearch([1,5,7,9,10,20], 20);
console.log(result);

// RecursivelyBinarySearch([1,5,7,9,10,20], 20) RecursivelyBinarySearch 返回 0，但我希望它为 5，是否可以在不传递原始数组的情况下执行此操作？

标签： javascriptrecursiondata-structures

Answer 1

欢迎来到堆栈溢出！不传递原始数组是一个奇怪的请求。但我认为你有一个很好的理由:)

关于您的代码段，您的二进制搜索功能中有错误。对于最后一种 else 情况，您需要通过arr.slice(0, middle)而不是middle - 1.

现在对于您的原始问题，我们每次都需要传递数组的第一个索引，因为此信息对于找到原始索引至关重要（执行 arr.slice 时它会丢失）。您可以像下面这样修改您的功能以获得所需的结果。

function getMiddle({right,left}) {
  return Math.floor((left + right) / 2);
}

function RecursivelyBinarySearch(arr, search, first_idx) {
  let left = 0;
  let right = arr.length - 1;
  let middle = getMiddle({left,right});
  if (right >= left) {
    if (arr[middle] === search) {
      return middle + first_idx;
    } else if (arr[middle] < search) {
      return RecursivelyBinarySearch(arr.slice(middle + 1, arr.length), search, middle + first_idx + 1);
    } else {
      return RecursivelyBinarySearch(arr.slice(0, middle), search, first_idx)
    }
  }
  return -1;
}

let result = RecursivelyBinarySearch([1,5,7,9,10,20], 20, 0);
console.log(result);