enperezzeledon

Suppose you have an list of distinct elements which has been sorted and rotated. How would you look up an element within that list? For example, the list: [7, 11, 13, 19, 2, 3, 5] is sorted (the first 7 primes, in order) and rotated (to put 7 first). With this list as input, then: look up 13 returns 2 since 13 is at index 2 look up 2 returns 4 look up 4 returns the sentinel value -1 The obvious technique is to just search the list: def lookup(values, v): try: return values.index(v) except IndexError: return -1 This is a linear algorithm which processes the entire list. Is there…

In the previous article I noted that Python’s heapq module is the only part of standard Python I could think of which deals with sorting, but which doesn’t give you full control over the sort order. That means you need to take care when using a heapq as a priority queue. For example, the A* search algorithm is a best first path finder. It maintains a priority queue of possible steps to take, ordered by an estimate of the total distance of the path routed through these steps. At each stage it pops the next step — the one with the shortest estimated total distance — from the queue, then…