Source code online books for professionals by professionals

Figure 6-5.  Dividing, recursing, and combining in a divide-and-conquer algorithm
3
For example, in the skyline problem, you would probably want to split the base case element (L,H,R) into two pairs, (L,H) and 
(R,H), so the combine function can build a sequence of points.
Searching by Halves
Before working through some more examples that fit the general pattern, let’s look at a related pattern, which discards one 
of the recursive calls. You’ve already seen this in my earlier mentions of binary search (bisection): It divides the problem 
into two equal halves and then recurses on only one of those halves. The core principle here is still balance. Consider what 
would happen in a totally unbalanced search. If you recall the “think of a particle” game from Chapter 3, the unbalanced 
solution would be equivalent to asking “Is this your particle?” for each particle in the universe. The difference is still 
encapsulated by Figures 
6-1
 and 
6-2
, except the work in each node (for this problem) is constant, and we only actually 
perform the work along a path from the root to a leaf.
Binary search may not seem all that interesting. It’s efficient, sure, but searching through a sorted sequence ... isn’t 
that sort of a limited area of application? Well, no, not really. First, that operation in itself can be important as a component 
in other algorithms. Second, and perhaps as importantly, binary search can be a more general approach to looking for 
things. For example, the idea can be used for numerical optimization, such as with Newton’s method, or in debugging 
your code. Although “debugging by bisection” can be efficient enough when done manually (“Does the code crash before 
it reaches this print statement?”), it is also used in some revision control systems (RCSs), such as Mercurial and Git.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
119
It works like this: You use an RCS to keep track of changes in your code. It stores many different versions, and you 
can “travel back in time,” as it were, and examine old code at any time. Now, say you encounter a new bug, and you 
understandably enough want to find it. How can your RCS help? First, you write a test for your test suite—one that will 
detect the bug if it’s there. (That’s always a good first step when debugging.) You make sure to set up the test so that 
the RCS can access it. Then you ask the RCS to look for the place in your history where the bug appeared. How does it 
do that? Big surprise: by binary search. Let’s say you know the bug appeared between revisions 349 and 574. The RCS 
will first revert your code to revision 461 (in the middle between the two) and run your test. Is the bug there? If so, you 
know it appeared between 349 and 461. If not, it appeared between 462 and 574. Lather, rinse, repeat.
This isn’t just a neat example of what bisection can be used for; it also illustrates a couple of other points 
nicely. First, it shows that you can’t always use stock implementations of known algorithms, even if you’re not really 
modifying them. In a case such as this, chances are that the implementors behind your RCS had to implement the 
binary search themselves. Second, it’s a good example of a case where reducing the number of basic operations can 
be crucial—more so than just implementing things efficiently. Compiling your code and running the test suite is likely 
to be slow anyway, so you’d like to do this as few times as possible.