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.
