bin-search for Python

Find function for sorted lists. In a sorted list we can do better than using 'find' which must look at each element in the array in turn. In this function we jump right in the middle of the array. If the middle element is the one we want, we're done. Otherwise, we search in the left or the right half of the vector. This depends on whether the object was less than or greater than the middle element. This example is taken from Paul Graham's 'ANSI Common Lisp', ch 4.

-----------------------

def binSearch(obj, vec):
    l = len(vec)
    if l != 0:
        return finder(obj, vec, 0, l-1)

def finder(obj, vec, start, end):
    r = end - start
    if r == 0:
        if obj == vec[int(start)]:
            return obj
        else:
            return 0
    else:
        mid = start + round(r / 2)
        obj2 = vec[int(mid)]
        if obj < obj2:
            return finder(obj, vec, start, mid-1)
        else:
            if obj > obj2:
                return finder(obj, vec, mid+1, end)
            else:
                return obj

Breadth first python script

Simple implementation of 'breadth-first search'. This implementation is based on the Common Lisp version in Paul Graham's 'ANSI Common Lisp'.

'm' is a network. We can try to find the shortest path from 'a' to 'd' with:

> shortestPath('a', 'd', m)

----------------------------------------------

m = [['a', 'b', 'c'], ['b', 'c'], ['c', 'd']]

def shortestPath(start, end, network):

    return bfs(end, [[start]], network)

def bfs(end, queue, network):

    if queue == []:

        return 0

    else:

        print queue

        path = queue[0]

        print path

        node = path[0]

        print node

        if node == end:

            return path[::-1]

        else:

            return bfs(end, queue[1:] + newPaths(path, node, network), network)

def newPaths(path, node, network):

    return map(lambda n: [n] + path, assoc(node, network)[1:])

def assoc(key, lst):

    pair = lst[0]

    if key == pair[0]:

        return pair

    else: return assoc(key, lst[1:])

check dit: http://orgmode.org/