Ladder Range

July 25, 2017

Once a year, or thereabouts, I pick up Jon Bentley’s book Programming Pearls and read a random chapter; even though I’ve read it before, re-reading always makes the material seem fresh. Today’s exercise is Exercise 7 from Chapter 4 about binary search:

A colleague faced the following problem in a program to draw lines on a bit-mapped display. An array of n pairs of reals (ai, bi) defined the n lines y = mi x +
bi. The lines were ordered in the x-interval [0, 1] in the sense that yi < yi+1 for all values of i between 0 and n − 2 and all values of x in [0, 1].

[ Here Bentley has a picture of a ladder with rungs at various angles to the horizontal. We won’t reproduce it here; get the book if you want to see it. ]

Less formally, the lines don’t touch in the vertical slab. Given a point (x, y), where 0 ≤ x ≤ 1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

Your task is to write a program to solve Bentley’s exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2