# Binary Search Algorithm in JavaScript

I've written this implementation of a binary search algorithm, and wanted to know if it was efficient and where I can improve.

function search(el, list) {
// list = list || LIST;
var LIM = Math.ceil(Math.log2(list.length)),
lb = 0,
ub = list.length - 1,
i;
while (el !== list[i = ~~((lb + ub) / 2)] && el !== list[++i]) {
if (el > list[i]) lb = i;
else ub = i;
}
return i;
}

• (I'd like to give an answer, but must put it in a comment due to 'on-hold' status.) Too many calculations! Don't do log2or (lb + ub) / 2. Instead, just start from lb=0 and len=list.length and while len>0 iterate testing list[lb + (h = ~~(len/2))], then either shorten the range to the left part: len = h or move to the right part: lb += 1 + h, len -= 1 + h, depending on less-than or greater-than result. Commented Dec 28, 2016 at 18:36
• This question is being discussed on meta Commented Dec 28, 2016 at 19:13
• To all who voted to close, the original posted contained the line ~~(...) + 1 which I edited to Math.ceil(...) ; however, they're not 100% equivalent - Math.ceil(0) = 0 where as ~~(0) + 1 = 1
– Tobi
Commented Dec 28, 2016 at 23:28
• In addition to all the other bugs that have been found, search(1, [1, 2, 3, 4]) returns not found instead of 0. The problem is that the upper bound is being set too high due to the ++i. The whole ++i part is not even necessary to begin with if you just set the bounds correctly and detect termination correctly.
– JS1
Commented Dec 30, 2016 at 11:35

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 is 0
• after the while() expression didn't find a match, --LIM gives -1, which evaluates to true
• 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 somewhat cryptic.
For the sake of readability you'd better to change:

• el to searchedValue
• LIM to tries (also note that using uppercase is supposed to be reserved for constants, while this data is not)
• lb to lowerBound
• ub to upperBound

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) {
}
if (searchedValue > list[i]) {
lowerBound = i;
} else {
upperBound = i;
}
}
return i;
}


(Note: Roland Illig points out this algorithm is wrong, so I wrote this answer under the assumption it was correct.)

# Naming

I think I understand what LIM is, many people would argue you should probably just write it out as LIMIT. However, these 3:

    lb = 0,
ub = list.length - 1,
i;


I have no idea what they mean. I would write out the names.

# log2

var LIM = Math.ceil(Math.log2(list.length))


It appears you are using LIM to provide a termination point for your program. You really don't need this for a binary search. It is unnecessarily complicated. I think you should think more about what you should do instead of me just telling you what the alternative is. Get rid of log2/LIM altogether.

# One-liners

This line:

el !== list[i = ~~((lb + ub) / 2)] && el !== list[++i]


Is really hard to understand. Unless you have a good reason to write code like this I wouldn't do it. I haven't seen a binary search that has a line this cryptic. There should be a way of breaking this up into multiple lines.

# Debugging

Given you were confused about the output, splitting up into multiple line might be a good thing as it allows you to isolate where the issue is better.

It produces an out-of-bounds access when you call search(3, [2]).