Как найти элементы в массиве JavaScript, где 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

Чтобы сделать это рекурсивно, вы, вероятно, захотите рекурсивно обрабатывать все меньшие и меньшие массивы, но это означает, что вам также нужно обновлять индекс, который вы проверяете при каждом вызове. Один из самых простых способов сделать это - просто включить индекс в параметры вашей функции и увеличивать его при каждом рекурсивном вызове. Это один из способов:

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)

Есть потенциальная проблема. Выполняя это над большим массивом, мы могли бы достичь предела глубины рекурсии. Если бы функция была хвостовой рекурсивной , эта проблема просто исчезла бы sh, когда JS движки выполняют оптимизацию хвостового вызова. Мы, конечно, не знаем, когда это произойдет, и даже если это действительно когда-либо произойдет, хотя это было оговорено в течение пяти лет. Но иногда имеет смысл написать, чтобы воспользоваться этим, в надежде, что когда-нибудь это станет реальностью, тем более что они все еще будут работать так же, как и версия без хвостового вызова.

Итак, хвостовая рекурсивная версия может выглядеть так:

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

Answer 2

Решение idiomati c в 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 ])) // []

Выше должно быть ясно, что рекурсия не требуется для задания. Но ничто не мешает вам использовать его, если вы используете sh -

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 3

Вы можете решить эту проблему без дополнительных временных массивов и параметров, просто сокращая массив на каждом шаге:

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 4

Для рекурсии вам понадобится конечное условие. Что-то вроде

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 5

Если вы хотите найти все элементы, вы должны начать с начала массива, а не с середины и l oop по всем индексам.

Идея состоит в том, чтобы рекурсия определить конечное условие .

Затем вы проверяете, нужно ли 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 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);