algorithm design and recursion the heart of the algorithm is loop that looks at the item in the middle of the remaining range to compare it to if is smaller than the middle itemthen we move highso that the search is narrowed to the lower half if is largerthen we move lowand the search is narrowed to the upper half the loop terminates when is found or there are no longer any more places to look ( low highhere is the codedef search(xnums)low high len(nums while low <highmid (low high)// item nums[midif =item return mid elif itemhigh mid elselow mid return - there is still range to search position of middle item found itreturn the index is in lower half of range move top marker down is in upper half move bottom marker up no range left to searchx is not there this algorithm is quite bit more sophisticated than the simple linear search you might want to trace through couple of example searches to convince yourself that it actually works comparing algorithms so farwe have developed two solutions to our simple searching problem which one is betterwellthat depends on what exactly we mean by better the linear search algorithm is much easier to understand and implement on the other handwe expect that the binary search is more efficientbecause it doesn' have to look at every value in the list intuitivelythenwe might expect the linear search to be better choice for small lists and binary search better choice for larger lists how could we actually confirm such intuitionsone approach would be to do an empirical test we could simply code up both algorithms and try them out on various sized lists to see how long the search takes these algorithms are both quite shortso it would not be difficult to run few experiments when tested the algorithms on my particular computer ( somewhat dated laptop)linear search was faster for lists of length or lessand there was not much noticeable difference in the range of length - after thatbinary search was clear winner for list of million elementslinear search averaged seconds to find random valuewhereas binary search averaged only seconds the empirical analysis has confirmed our intuitionbut these are results from one particular machine under specific circumstances (amount of memoryprocessor speedcurrent loadetc how can we be sure that the results will always be the sameanother approach is to analyze our algorithms abstractly to see how efficient they are other factors being equalwe expect the algorithm with the fewest number of "stepsto be the more