exercises
exercises copied to clipboard
Lookup count in binary-search test is not correct
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!
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.
@Tadwork You brought a very good point.
My solution ended up with 11 lookups. Merging the PR would be good.