如何在 arrayJavaScript where 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

如果您想查找所有元素，您应该从数组的开头开始，而不是从中间开始并遍历所有索引。

递归的思路是定义结束条件。

然后检查 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 2

我不知道你为什么要通过递归：- 但无论如何，以下内容应该对您有所帮助：-

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);

Answer 3

对于递归，您需要一个结束条件。像

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 4

您可以通过在每个步骤中简单地缩短数组来解决这个 w/o 额外的临时数组和参数：

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 5

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 6

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

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)

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

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

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

如何在 arrayJavaScript where array[i] = i 中查找元素？

How to find elements in array JavaScript where array[i] = i?

javascript

arrays

sorting

recursion

binary-search