Binary Search Algorithm in JavaScript

Question

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 (!--LIM) return ("NOT FOUND");
        if (el > list[i]) lb = i;
        else ub = i;
    }
    return i;
}

Answer 1

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

Answer 2

(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.

Answer 3

Your algorithm is wrong.

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