What doesn't work properly
As pointed by @Roland Illig's answer, your solution produces an error when list
contains only 1 item and this item doesn't match el
.
It comes from the fact that:
- for a 1-item list,
LIM
is0
- after the
while()
expression didn't find a match,--LIM
gives-1
, which evaluates totrue
- so
if (!--LIM)
is false and the loop continues infinitely...
This issue can be solved by merely changing this test to if (--LIM <= 0)
Possible improvements
As pointed by @Dair, your names are somesomewhat cryptic.
For the sake of readability you'd better to change:
el
tosearchedValue
LIM
totries
(also note that using uppercase is supposed to be reserved for constants, while this data is not)lb
tolowerBound
ub
toupperBound
Also, following best practices, I recommend to use block marks for if()
s.
All that said, here is a suggested improved (and corrected) version:
function search(searchedValue, list) {
var tries = Math.ceil(Math.log2(list.length)),
lowerBound = 0,
upperBound = list.length - 1,
i;
while (
searchedValue !== list[i = ~~((lowerBound + upperBound) / 2)]
&&
searchedValue !== list[++i]
) {
if (--tries <= 0) {
return ("NOT FOUND");
}
if (searchedValue > list[i]) {
lowerBound = i;
} else {
upperBound = i;
}
}
return i;
}