John Paul Mueller - Algorithms For Dummies

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 aListcontaining the numbers 1 through 20. It searches for a value of 5in 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 keymatches the midpoint, the value is found in the list and the recursion ends.

Note that this example makes one of two recursive calls. When keyis greater than the midpoint value of the existing list, searchList[mid], the code calls searchagain with just the right side of the remaining list. In other words, every call to searchuses just half the list found in the previous call. When keyis 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 searchListto 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 searchListcontent. When working with recursion, you must remain proactive or endure the consequences later.

Recursion is part of many different algorithmic programming solutions, as you see in the upcoming chapters. In fact, it’s hard to get away from recursion in many cases because an iterative approach proves nonintuitive, cumbersome, and time consuming. However, you can create a number of different versions of the same solution, each of which has its own characteristics, flaws, and virtues.

The solution that this chapter doesn’t consider is sequential search, because a sequential search generally takes longer than any other solution you can employ. In a best-case scenario, a sequential search requires just one comparison to complete the search, but in a worst-case scenario, you find the item you want as the last check. As an average, sequential search requires (n+1)/2checks or O(n)time to complete. (The “ Working with functions” section of Chapter 2tells you more about big-O notation.)

The binary search in the previous section does a much better job than a sequential search does. It works on logarithmic time or O(log n). In a best-case scenario, it takes only one check, as with a sequential search, but the output from the example shows that even a worst-case scenario, where the value doesn’t even appear in the list, takes only six checks rather than the 21 checks that a sequential search would require.

If you look at performance times alone, however, the data you receive can mislead you into thinking that a particular solution will work incredibly well for your application when in fact it won’t. You must also consider the kind of data you work with, the complexity of creating the solution, and a host of other factors. That’s why later examples in this book also consider the pros and cons of each approach — the hidden dangers of choosing a solution that seems to have potential and then fails to produce the desired result.

Текст предоставлен ООО «ЛитРес».