Читать книгу Algorithms For Dummies - John Paul Mueller, John Mueller Paul, Luca Massaron - Страница 96

Some problems look overwhelming when you start them. Take, for example, writing 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 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. 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 letter H in Hello is less than M in the alphabet, 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 splitting 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 determine 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.

def search(searchList, key): mid = int(len(searchList) / 2) print("Searching midpoint at ", str(searchList[mid])) if mid == 0: print("Key Not Found!") return key elif key == searchList[mid]: print("Key Found!") return searchList[mid] elif key > searchList[mid]: print("searchList now contains ", searchList[mid:len(searchList)]) search(searchList[mid:len(searchList)], key) else: print("searchList now contains ", searchList[0:mid]) search(searchList[0:mid], key) aList = list(range(1, 21))search(aList, 5)

When you run this code, you see this output:

Searching midpoint at 11searchList now contains [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Searching midpoint at 6searchList now contains [1, 2, 3, 4, 5]Searching midpoint at 3searchList now contains [3, 4, 5]Searching midpoint at 4searchList now contains [4, 5]Searching midpoint at 5Key Found!

This recursive approach to the binary search begins with aList containing the numbers 1 through 20. It searches for a value of 5 in aList. Each iteration of the recursion begins by looking for the list's midpoint, mid, and then using that midpoint to determine the next step. When the key matches the midpoint, the value is found in the list and the recursion ends.

Note that this example makes one of two recursive calls. When key is greater than the midpoint value of the existing list, searchList[mid], the code calls search again with just the right side of the remaining list. In other words, every call to search uses just half the list found in the previous call. When key is less than or equal to searchList[mid], search receives the left half of the existing list.

The list may not contain a search value, so you must always provide an escape method for the recursion or the stack (a special area of memory used to store the call information; see https://www.geeksforgeeks.org/stack-vs-heap-memory-allocation/ for details) will fill, resulting in an error message. In this case, the escape occurs when mid == 0, which means that there is no more searchList to search. For example, if you change search(aList, 5) to search(aList, 22), you obtain the following output instead:

Searching midpoint at 11searchList now contains [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]Searching midpoint at 16searchList now contains [16, 17, 18, 19, 20]Searching midpoint at 18searchList now contains [18, 19, 20]Searching midpoint at 19searchList now contains [19, 20]Searching midpoint at 20searchList now contains [20]Searching midpoint at 20Key Not Found!

Note also that the code looks for the escape condition before performing any other work to ensure that the code doesn't inadvertently cause an error because of the lack of searchList content. When working with recursion, you must remain proactive or endure the consequences later.