Algorithms For Dummies. John Paul Mueller
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.
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 Кошелек, бонусными картами или другим удобным Вам способом.