Lookup count in binary-search test is not correct

[PinkyJie]

First of all, thanks for this wonderful project.

When I started to do the binary-search challenge, I found there maybe some issues about the last test(the lookup count one). I have written 2 implementations, both implementations has passed all the tests except last one.

First one: the lookup count is 5000 in this implementation. I think maybe it is because the native implementation of array.slice has touched the get property. So I implemented the second one.

function search(arr, ele) {
  var len = arr.length;
  if (len === 0) {
    return -1;
  }

  var middleIdx = Math.floor(len / 2);
  if (arr[middleIdx] > ele) {
    return search(arr.slice(0, middleIdx), ele);
  } else if (arr[middleIdx] < ele) {
    var res = search(arr.slice(middleIdx + 1), ele);
    if (res === -1) {
      return -1;
    }
    return middleIdx + 1 + res;
  } else {
    return middleIdx;
  }
}

Second one: the lookup count is 11, not 13.

function search(arr, ele) {
  var len = arr.length;
  if (len === 0) {
    return -1;
  }

  function _search(startIdx, endIdx) {
    if (startIdx === endIdx && arr[startIdx] !== ele) {
      return -1;
    }
    var middleIdx = startIdx + Math.floor((endIdx - startIdx) / 2);
    if (arr[middleIdx] > ele) {
      return _search(startIdx, middleIdx);
    } else if (arr[middleIdx] < ele) {
      return _search(middleIdx + 1, endIdx);
    } else {
      return middleIdx;
    }
  }

  return _search(0, len);
}

So I guess maybe 13 is not correct. Could you help me to check this out? Thanks!

[Tadwork]

It seems like the test is biased toward a simpler implementation of a binary-search that just checks if the value is greater or less than the middle and recurses such as https://github.com/Tadwork/exercises/blob/master/binary-search/index.js#L23 if however there is an extra check to see if the middle value is the number we are looking for ( https://github.com/Tadwork/exercises/blob/master/binary-search/index.js#L13 ) that will change the number of times the search function is called and the lookup count.

I think the two implementations are of similar O(log(n)) complexity and the extra check amounts to a constant change... it might pay to check for 11 or 13 or even just to add a comment , but changing the test will break it for those who implement the simpler (but still correct) way.

[PinkyJie]

@Tadwork You brought a very good point.

[jsumners]

My solution ended up with 11 lookups. Merging the PR would be good.