时间戳

首页 > 解决方案 > 如何在数组 JavaScript 中找到数组 [i] = i 的元素？

javascript - 如何在数组 JavaScript 中找到数组 [i] = i 的元素？

问题描述

我需要在数字数组中查找元素 where arr[i] === i，这意味着元素必须等于数组索引。
必须使用递归找到它们，而不仅仅是循环。
如果有人提供帮助，我将非常感激，因为我花了很多时间却无能为力。
我尝试使用二分搜索，但它不起作用。最后我只有空数组。 

function fixedPointSearch(arr, low, high) {

  let middle = Math.floor((high - low) / 2);
  
  console.log(  low, high, middle )
  
  let arrRes = [];
  if (arr[middle] === middle)
    { arrRes.push(arr[middle]); }
  else if (arr[middle] > middle)
    { fixedPointSearch(arr, middle + 1, high); }
  else
    { fixedPointSearch(arr, low, middle - 1); }

  return arrRes;
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];
console.log(fixedPointSearch(arr1, 0, arr1.length - 1));

标签： javascriptarrayssortingrecursionbinary-search

解决方案

要递归地执行此操作，您可能希望对越来越小的数组进行递归，但这意味着您还需要更新每次调用时检查的索引。最简单的方法之一就是在函数的参数中包含一个索引，并在每次递归调用时递增它。这是这样做的一种方法：

const fixedPointSearch = ([x, ...xs] = [], index = 0) =>
  x == undefined
    ? [] 
    : [... (x === index ? [x] : []), ... fixedPointSearch (xs, index + 1)]

console .log (
  fixedPointSearch([-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17])
)

该版本或以下版本是否更易于阅读尚有争议，但它们本质上是在做同样的事情：

const fixedPointSearch = ([x, ...xs] = [], index = 0) =>
  x == undefined
    ? [] 
  : x === index
    ? [x, ... fixedPointSearch (xs, index + 1)]
  : // else 
    fixedPointSearch (xs, index + 1)

但是，有一个潜在的问题。在一个大数组上运行它，我们可以达到递归深度限制。如果函数是尾递归的，那么当 JS 引擎执行尾调用优化时，这个问题就会消失。当然，我们不知道那会是什么时候，甚至它实际上会发生，即使它已经指定了五年。但有时写作以利用它是有意义的，希望有一天它会成为现实，特别是因为这些仍然可以像非尾调用版本一样工作。

所以尾递归版本可能如下所示：

const fixedPointSearch = ([x, ...xs] = [], index = 0, res = []) =>
  x == undefined
    ? res
    : fixedPointSearch (xs, index + 1, x === index ? [...res, x] : res)

推荐阅读