Question

A technique for speeding up iterations of this algorithm involves augmenting each node in a catalog graph with one over d elements from each adjacent node, where d is a degree bound. That technique, called fractional cascading, (15[1])lets you run this algorithm once and get the rest in constant time. Most cheap analog-to-digital converters use a successive approximation register architecture, which implements this algorithm. An anecdote in Programming Pearls notes that, given a couple hours, 90 percent of programmers still (*) failed to (10[1])correctly implement this algorithm. The user specifies “bad” or “good” to determine which commit (10[1])introduced a bug in a git (10[1])tool that implements this algorithm. Most implementations (10[1])of this algorithm repeatedly set a middle variable to the average of low and high variables. For 10 points, name this algorithm that finds an object in a sorted list by repeatedly dividing it in half. ■END■

Back to tossups