Algorithms For Dummies

Considering divide and conquer

Some problems look overwhelming when you start them. Take, for example, writ-

ing a book. If you consider the entire book, writing it is an overwhelming task. 

However, if you break the book into chapters and consider just one chapter, the 

---

108

 

   

  PART 1 

 Getting Started

problem seems a little more doable. Of course, an entire chapter can seem a bit 

daunting, too, so you break the task down into first-level headings, which seems 

even more doable, but still not quite doable enough. The first-level headings could 

contain second-level headings and so on until you have broken down the problem 

of writing about a topic into short articles as much as you can. Even a short article 

can seem too hard, so you break it down into paragraphs, then into sentences, and 

finally into individual words. Writing a single word isn’t too hard. So, writing a 

book comes down to writing individuals words —lots of them. This is how divide 

and conquer works. You break a problem down into smaller problems until you 

find a problem that you can solve without too much trouble.

Computers can use the divide-and-conquer approach as well. Trying to solve a 

huge  problem  with  an  enormous  dataset  could  take  days  —  assuming  that  the 

task  is  even  doable.  However,  by  breaking  the  big  problem  down  into  smaller 

pieces,  you  can  solve  the  problem  much  faster  and  with  fewer  resources.  For 

example, when searching for an entry in a database, searching the entire database 

isn’t necessary if you use a sorted database. Say that you’re looking for the word 

Hello in the database. You can begin by splitting the database in half (letters A 

through M and letters N through Z). The numeric value of the H in Hello (a value of 

72 when using a standard ASCII table) is less than M (a value of 77) in the alpha-

bet, so you look at the first half of the database rather than the second. Splitting 

the remaining half again (letters A through G and letters H through M), you now 

find that you need the second half of the remainder, which is now only a quarter 

of the database. Further splits eventually help you find precisely what you want by 

searching only a small fraction of the entire database. You call this search approach 

a binary search. The problem becomes one of following these steps:

1. 

Split the content in question in half.

2. 

Compare the keys for the content with the search term.

3. 

Choose the half that contains the key.

4. 

Repeat Steps 1 through 3 until you find the key.

Most divide-and-conquer problems follow a similar approach, even though some 

of these approaches become quite convoluted. For example, instead of just split-

ting the database in half, you might split it into thirds in some cases. However, the 

goal is the same in all cases: Divide the problem into a smaller piece and deter-

mine whether you can solve the problem using just that piece as a generalized 

case. After you find the generalized case that you know how to solve, you can use 

that piece to solve any other piece as well. The following code shows an extremely 

simple version of a binary search that assumes that you have the list sorted. (You 

can find this code in the 

A4D; 05; Binary Search.ipynb

 file on the Dummies site 

as part of the downloadable code; see the Introduction for details.)

---

CHAPTER 5