I’m reading Data Structures and Algorithms in Python, by Goodrich, Tamassia, and Goldwasser, and I think that it is very, very good. I particularly like the explanation of why binary search over a sorted list is .
Basically, whenever you repeatedly cut your search space in half, then you produce performance. This is because the number of times you need to halve before you get something less than or equal to 1 is . Think of it this way, if we solve for the smallest , then we’ve found the number of times we need to halve . Then we multiply both sides by and we get . Then we take the log base 2 of both sides and we obtain . Think of the as saying, “yeah, for is also less than or equal to one, but that’s not interesting”.
The motivation for binary search over sorted data versus a sequential search over unsorted data is that with the former option we obtain time complexity, whereas with the later we are stuck with time complexity.
The binary search algorithm is singly recursive, and in particular, tail call recursive, since it returns itself rather than some function of itself. By contrast, a recursive factorial function would return something like
n*factorial(n-1), and a recursive Fibonacci function would return something like
fib(n-1)+fib(n-2), which are a functions of themselves. Although all recursive functions can be implemented iteratively, tail call recursive functions are particularly easy to convert into an iterative form.
x = [ 2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33, 37 ] def binarySearch( data, target, low=None, high=None ): if low == None and high == None: low, high = 0, len(data)-1 if low > high: return -1 else: midpoint = (high+low)/2 if target == data[midpoint]: return midpoint elif target < data[midpoint]: return binarySearch( data, target, low, midpoint-1 ) elif target > data[midpoint]: return binarySearch( data, target, midpoint+1, high ) # out of lower bound assert binarySearch( x, 0 ) == -1 # lower limit assert binarySearch( x, 2 ) == 0 # non-extant target assert binarySearch( x, 3 ) == -1 # extant target assert binarySearch( x, 5 ) == 2 # upper limit assert binarySearch( x, 37 ) == 15 # out of upper bound assert binarySearch( x, 40 ) == -1