Find the first element that equals its index

Question

Can anyone help me improve the performance of my code.

Given a sorted array of distinct integers, write a function indexEqualsValue that returns the lowest index for which array[index] == index. Return -1 if there is no such index.

function indexEqualsValue(a) {
  var arr =[]
  
  a.forEach((el, i) => {
  if( el==i){
    arr.push(el)
  }
   })
if(arr.length==0){
  return -1
}else{
  return arr[0]
}
 
}

Answer 1

Assuming the input is sorted in ascending order, if a[i] > i then a[j] > j for any j >= i, because the numbers in the input are supposed to be distinct.

There is also no reason to aggregate all values that satisfy the criterion to eventualy only return the first one. Just return the first one when encountered.

function indexEqualsValue(input)
{
  const limit = input.length
  for (let i = 0; i < limit; ++i) {
    if (input[i] === i) {
        return i
    }
    
    if (input[i] > i) {
        return -1
    }
  }
  
  return -1
}

console.log(indexEqualsValue([0,1,2])) // 0
console.log(indexEqualsValue([1,2,3])) // -1
console.log(indexEqualsValue([-1,1,2])) // 1

A bit of complexity analysis:

Your solution is O(n) in time and O(k) in space, where n is size of input, and k is number of elements that satisfy the criterion a[i]==i, k <= n.

My solution is O(b) in time, and O(1) in space, where b is number of elements that satisfy a similar criterion: a[i] < i, in words, the number of elements that are less then their index, b <= n. If input does not contain negative numbers, it is O(1) in time (thats actually because in that case the result must be zero, or -1).

PS: Next time, please, take your time to write a good quality question. Succint algorithm definition without any additional information makes up for a very poor question. You're lucky I'm in mood.