Monday, August 18, 2014

Find the greatest value in a list less than a value

Binary search must be one of the most useful and simplest of algorithms. It allows you to find an element in a sorted list that is either there or not. But what if you want to put an element in the list, one position after the next less or equal element? I would have thought that to be a common enough requirement, but I can't find any implementations on the Web that make any sense, or which are more efficient that just iterating through the list and noting the last less-than-or-equal-to-value.

In my case I had to find the scroll position in a HTML div, which was marked at intervals by "page-breaks". Each page-break marked the start of a new page and I wanted to find out which page the display was on. To do that I kept a list of where each page-break began in pixels down the div, and then I needed to look up quickly the highest value in the list, the page-break, that was less than or equal to the given scroll position. Here's what I came up with in Java. Adapt as you see fit to other languages.


  1. Are you sure, that binsearch ist fastest?

    Had a similar problem, where I benchmarked other solutions against binsearch O(log N), grep O(N) and sequential search O(N/2) in Perl. Binsearch was significantly slower than the other two. Actual implementations are hardware friendly or not, but hardware knows nothing about "big O".

  2. binsearch ist absolut der schnellste...

    But the code above is not pure binary search, so there is actually no routine I know to compare it with.
    WIth perl you have the overhead of converting the script into executable code, reading the arguments (off disk?) and you are also at the mercy of whoever wrote the binarysearch routine. Hardware doesn't have to "know anything" about big O it just executes instructions, and the fastest instructions will work the fastest.
    You have to compare like with like rigorously and I don't see from your description that you've done that.