如何在数组中查找 array[i] = i 的元素？

Question

我需要在一个数组中查找元素，其中的 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));

Answer 1

你可以通过简单地缩短每一步中的数组来解决这wo额外的临时数组和参数。

const myArray = [0, 5, 2, 4, 7, 9, 6];

function fixedPointSearch(arrayToTest) {
  if (arrayToTest.length === 0) {
    return [];
  }

  const lastIndex = arrayToTest.length - 1;
  const lastItem = arrayToTest[lastIndex];
  const remainingItems = arrayToTest.slice(0, lastIndex);

  return lastItem === lastIndex
    ? [...fixedPointSearch(remainingItems), lastItem]
    : fixedPointSearch(remainingItems);
}

console.log(fixedPointSearch(myArray));

Answer 2

要做到这一点，你大概想在越来越小的数组上递归， 但这意味着你需要更新你在每次调用时检查的索引。 最简单的方法之一就是在函数的参数中包含一个索引，并在每次递归调用时递增它。 这是一种方法。

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)

Answer 3

如果你想找到所有的元素 你应该从数组的开头开始，而不是从中间开始 然后在所有的索引中循环。

递归的想法是定义了 结束条件.

然后你检查是否 arr[i] === i 以更新 results 数组。

然后我们进行递归调用，索引递增，更新后的 results 数组。

function fixedPointSearch(arr, i, results) {
  // End condition of the recursion
  if (i === arr.length - 1 || arr.length === 0) {
    return results;
  }
  
  if (arr[i] === i) {
    results.push(i);
  }
  
  // Recursive call
  return fixedPointSearch(arr, i + 1, results);
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];

console.log(fixedPointSearch(arr1, 0, []));
console.log(fixedPointSearch([], 0, []));
console.log(fixedPointSearch([9, 8, 7], 0, []));

Answer 4

JavaScript中的惯用方案是使用 Array.prototype.filter -

const run = (a = []) =>
  a.filter((x, i) => x === i)

console.log(run([ 0, 1, 2, 3, 4, 5 ])) // [0,1,2,3,4,5]
console.log(run([ 3, 3, 3, 3, 3, 3 ])) // [3]
console.log(run([ 7, 1, 7, 3, 7, 5 ])) // [1,3,5]
console.log(run([ 9, 9, 9, 9, 9, 9 ])) // []

上面应该很清楚，递归并不是工作所需要的。但是，如果你愿意的话，没有什么可以阻止你使用它------。

const filter = (test = identity, a = [], i = 0) =>
{ /* base */
  if (i >= a.length)
    return []
  
  /* inductive: i is in bounds */
  if (test(a[i], i))
    return [ a[i], ...filter(test, a, i + 1) ]
  
  /* inductive: i is in bounds, a[i] does not pass test */
  else
    return filter(test, a, i + 1)
}

const run = (a = []) =>
  filter((x, i) => x === i, a)

console.log(run([ 0, 1, 2, 3, 4, 5 ])) // [0,1,2,3,4,5]
console.log(run([ 3, 3, 3, 3, 3, 3 ])) // [3]
console.log(run([ 7, 1, 7, 3, 7, 5 ])) // [1,3,5]
console.log(run([ 9, 9, 9, 9, 9, 9 ])) // []

Answer 5

对于递归，你需要一个结束条件。比如说

const findElementValueIsPositionInarray = arr => {
  let results = [];
  const find = i => {
    if (arr.length) {             // as long as arr has values
       const value = arr.shift(); // get value
       results = i === value      // check it
        ? results.concat(value)
        : results;
       return find(i+1);          // redo with incremented value of i
    }
    return results;
  };  
  return find(0);
}
console.log(findElementValueIsPositionInarray([2,3,4,3,9,8]).join());
console.log(findElementValueIsPositionInarray([2,3,4,91,9,8]).join());
console.log(findElementValueIsPositionInarray([0,1,2,87,0,5]).join());

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 6

我不知道你为什么要通过递归来实现：-但无论如何，下面的内容应该对你有所帮助：-。

let ans = [];

function find(arr,index,ans)
{
  if(index==arr.length-1)
    {
      if(arr[index]==index){
        ans.push(arr[index])
    }
    return;
}
  if(arr[index]==index){
      ans.push(arr[index])
}
  find(arr,index+1,ans);
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];
find(arr1,0,ans);
console.log(ans);