This is an implementation of the binary search algorithm in (almost) one line. Given a number 'n' and a list 'L', the function returns the index of the number on the list, or -1.
1 2 3 4 5 6 7
def search(n, L): f = lambda n,L,o: len(L) and ( \ (n == L[len(L)/2])*(len(L)/2+o) or \ (n < L[len(L)/2] and f(n,L[:len(L)/2],o)) or \ (n > L[len(L)/2] and f(n,L[len(L)/2+1:],o+len(L)/2+1))) return f(n,L,1) - 1
I did this function for a series of programming katas (http://pragprog.com/pragdave/Practices/Kata/KataTwo.rdoc). The goal of the second kata is to come up with five unique approaches to a binary chop, one per day. I was curious if I could do it in one line, and here's the result.
I encountered some problems while developing it because 0 is a valid index, but its also a boolean false. Thats why I add an offset of 1 when calling the function, and subtract 1 later.
The function is only a little slower than other recursive or iterative implementations that I've tried.