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.
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.
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.
Distinguishing between different possible solutions
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)/2 checks or O(n) time to complete. (The “Working with functions” section of Chapter 2 tells 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.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.
