1

I need to find elements in an array of numbers where arr[i] === i, meaning the element must be equal to the array index.
They must be found with using recursion, not just by cycle.
I would be very thankful, if someone help, because I've spent many hours and can't do anything.
I've tried to use Binary Search but it doesn't work. In the end I've got only the empty array. 

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

Improve this question
6
  • You want to find all the elements that match their index or just one ? Commented May 6, 2020 at 15:56
  • Why do you need recursion here at all? If you want to find all elements where a[i] === i then you can simply .filter() the initial array using this condition. Commented May 6, 2020 at 15:56
  • @KirillSimonov Homework? Commented May 6, 2020 at 15:57
  • Binary search doesn't make sense when the array is not sorted. And it doesn't really make sense if you need to return multiple individual elements Commented May 6, 2020 at 16:06
  • arr.filter((x, i) => x === i) ought to do the trick Commented May 6, 2020 at 16:25

6 Answers 6

Reset to default
2

To do this recursively, you presumably want to recurse on smaller and smaller arrays, but that means you need to also update the index you're checking on each call. One of the simplest ways to do this is just to include an index in the parameters to your function and increment it on each recursive call. This is one way to do so:

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

It's debatable whether that version or the following one is easier to read, but they are doing essentially the same thing:

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

There is a potential problem, though. Running this over a large array, we could hit the recursion depth limit. If the function were tail-recursive, that problem would simply vanish when JS engines perform tail-call optimization. We don't know when that will be, of course, or even it it will actually ever happen, even though it's been specified for five years. But it sometimes makes sense to write to take advantage of it, on the hope that it will one day become a reality, especially since these will still work as well as the non-tail-call version.

So a tail-recursive version might look like this:

const fixedPointSearch = ([x, ...xs] = [], index = 0, res = []) =>
  x == undefined
    ? res
    : fixedPointSearch (xs, index + 1, x === index ? [...res, x] : res)
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Wow... What is "xs"?
The plural of x. :-) I usually use x for an item of an unknown type and xs for a collection of them. But, since these are assumed to be numbers, I really should have used n and ns. But in either case a parameter like [n, ...ns] represents an array with n holding the first item and ns an array with the remainder. This is quite useful when recursing over an array.
so that's interesting... filter can be implemented using reduce or flatMap. thanks Scott :D
@Thankyou: I hadn't made that connection either, but yes it could. And I've already used that notion in another answer. :-)
1

You can solve this w/o additional temporary arrays and parameters, by simply shortening the array in each step:

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

Improve this answer

Comments

1

If you want to find all the elements you should start from the beginning of the array, not the middle and loop through all the indexes.

The idea is for the recursion is to define the end condition.

Then you check if arr[i] === i to update the results array.

Then you make the recursive call with the index incremented and with the updated results array.

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, []));

Improve this answer

Comments

1

The idiomatic solution in JavaScript uses 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 ])) // []

Above it should be clear that recursion isn't required for the job. But there's nothing stopping you from using it, if you wish -

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 ])) // []

Improve this answer

Comments

1

For recursion, you'll need an end condition. Something like

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

Improve this answer

Comments

0

I don't know why you want it through recursion:- But anyway following should help you:-

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);
Improve this answer

3 Comments

It probably got downvoted because it is wrong and doesn't work. The ans variable is shadowed. Updating a global variable is bad and the function doesn't return anything, so multiple call to this function will produce a wrong output. The loose comparison allow things like ['0'] to be returned, or worse [false, true, true] that why the author asked for strict equality. It throws an error for empty arrays. Also it's written with a poor coding style it's not easy to read and understand and there is no explanation provided. It doesn't seem unfair at all.
I get it. I will take that as constructive criticism. Thank you :).
Take the time to provide explanations with your answers, don't post code only. Also try to have a good coding style so others can read your code easily, you can use spaces between keywords and operators for example. Take time to learn about basics and best practices of javascript medium.com/javascript-in-plain-english/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.