given the structure of this algorithmit is not surprising that the most straightforward implementation of binary search uses recursionas shown in figure def search(le)"""assumes is listthe elements of which are in ascending order returns true if is in and false otherwise""def bsearch(lelowhigh)#decrements high low if high =lowreturn [low= mid (low high)// if [mid=ereturn true elif [mideif low =mid#nothing left to search return false elsereturn bsearch(lelowmid elsereturn bsearch(lemid highif len( = return false elsereturn bsearch(le len( figure recursive binary search the outer function in figure search(le)has the same arguments as the function specified abovebut slightly different specification the specification says that the implementation may assume that is sorted in ascending order the burden of making sure that this assumption is satisfied lies with the caller of search if the assumption is not satisfiedthe implementation has no obligation to behave well it could workbut it could also crash or return an incorrect answer should search be modified to check that the assumption is satisfiedthis might eliminate source of errorsbut it would defeat the purpose of using binary searchsince checking the assumption would itself take (len( )time functions such as search are often called wrapper functions the function provides nice interface for client codebut is essentially pass-through that does no serious computation insteadit calls the helper function bsearch with appropriate arguments this raises the question of why not eliminate search and have clients call bsearch directlythe reason is that the parameters low and high have nothing to do with the abstraction of searching list for an element they are implementation details that should be hidden from those writing programs that call search let us now analyze the complexity of bsearch we showed in the last section that list access takes constant time thereforewe can see that excluding the recursive calleach instance of bsearch is ( thereforethe complexity of bsearch depends only upon the number of recursive calls