algorithm design and recursion guess nameyou tell me if your name comes alphabetically before or after the name guess how many guesses will you needour analysis above shows the answer to this question is log if you don' have calculator handyhere is quick way to estimate the result or roughly and that means that that is is approximately one million sosearching million items requires only guesses continuing onwe need guesses for two million for four million for eight millionand guesses to search among sixteen million names we can figure out the name of total stranger in new york city using only guessesby comparisona linear search would require (on average million guesses binary search is phenomenally good algorithmi said earlier that python uses linear search algorithm to implement its built-in searching methods if binary search is so much betterwhy doesn' python use itthe reason is that the binary search is less generalin order to workthe list must be in order if you want to use binary search on an unordered listthe first thing you have to do is put it in order or sort it this is another well-studied problem in computer scienceand one that we should look at before we turn to sortinghoweverwe need to generalize the algorithm design technique that we used to develop the binary search recursive problem-solving rememberthe basic idea behind the binary search algorithm was to successively divide the problem in half this is sometimes referred to as "divide and conquerapproach to algorithm designand it often leads to very efficient algorithms one interesting aspect of divide and conquer algorithms is that the original problem divides into subproblems that are just smaller versions of the original to see what meanthink about the binary search again initiallythe range to search is the entire list our first step is to look at the middle item in the list should the middle item turn out to be the targetthen we are finished if it is not the targetwe continue by performing binary search on either the top-half or the bottom half of the list using this insightwe might express the binary search algorithm in another way algorithmbinarysearch -search for in nums[lownums[highmid (low high/ if low high is not in nums elif nums[midperform binary search for in nums[lownums[mid- else perform binary search for in nums[mid+ nums[highrather than using loopthis definition of the binary search seems to refer to itself what is going on herecan we actually make sense of such thing