listing recursive implementation of the binary search algorithm performs recursive binary search on sorted sequence def recbinarysearchtargettheseqfirstlast )if the sequence cannot be subdivided furtherwe are done if first last base case # return false else find the midpoint of the sequence mid (last first/ does the element at the midpoint contain the targetif theseq[mid=target return true base case # or does the target precede the element at the midpointelif target theseq[midreturn recbinarysearchtargettheseqfirstmid or does it follow the element at the midpointelse return recbinarysearchtargettheseqmid last we evaluated the binary search algorithm in and found it required (log ntime in the worst case to determine the run time of recursive implementationwe must consider the time required to execute single invocation of the function and the number of times the function is called in evaluating the time of single function invocationwe use the same technique as we applied in previous and sum the times of the individual statements the recursive callshoweverare not included since their times will be computed separately for the recbinarysearch(functionwe can quickly determine that each non-recursive function call statement only requires ( time to help determine the number of times the recursive function is calledwe can use its recursive call tree consider the recursive call tree for the binary search algorithmas shown at the top of figure which results when searching for value in the sequence shown at the bottom of the figure the number of function call boxes in the tree for given sequence of length will indicate the total number of times the function is called there are two recursive calls to recbinarysearch(within the function bodybut only one will be executed for each invocation thusthere will be single function call box at each level in the call tree and we only have to determine how many levels there are in the call tree when searching sequence of items the worst case occurs when the target value is not in the sequencewhich can be determined when the first and last markers cross each other with first last as with the iterative version of the algorithmthe number of elements in the sorted sequence that must be searched is reduced by half each time the function is called we know from that repeatedly reducing the input size by half requires log reductions in order to reach the case where there are no additional elements to be searched thusthe recursive version of the binary search requires (log ntime in the worst case