2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ (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. \$\endgroup\$ – CiaPan Dec 28 '16 at 18:36
  • \$\begingroup\$ This question is being discussed on meta \$\endgroup\$ – janos Dec 28 '16 at 19:13
  • \$\begingroup\$ 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 \$\endgroup\$ – Tobi Dec 28 '16 at 23:28
  • \$\begingroup\$ 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. \$\endgroup\$ – JS1 Dec 30 '16 at 11:35
3
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Your algorithm is wrong.

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

|improve this answer|||||
\$\endgroup\$
  • 6
    \$\begingroup\$ This would have been better as a comment + vote to close as broken \$\endgroup\$ – janos Dec 28 '16 at 8:24
  • 2
    \$\begingroup\$ @Janos The original author appeared to be unaware that the code was broken, and it wasn't obviously broken enough to be closed as broken code. (As evidence, Dair missed the bug as well, and already wrote an answer.) Since this answer points out an issue with correctness in an unanticipated case, it is a fine answer. \$\endgroup\$ – 200_success Dec 29 '16 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.