Karate Chop

June 16, 2015

Dave Thomas has a Code Kata in which he challenges programmers to write five different implementations of binary search (also known as the “binary chop” or, in Thomas’ kata-lingo, the “karate chop”). He doesn’t define “different” except to use phrases such as “totally different technique” and “totally unique implementations” and to suggest the traditional iterative approach, a recursive approach, a functional style passing array slices around, and so on.

Your task is to write five different implementations of binary search, returning the index of a target value in a sorted array of integers, or -1 if the target is not present. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “Karate Chop”

  1. Mike said

    I don’t give the code for the standard interative, recursive and functional functions. But here is a somewhat different approach. Basically, for each bit in the index, starting at the msb, you decide whether that bit should be set or clear by comparing el with the value at lst[index with the bit set]. four() is an iterative version, five() is a recursive version; nine() is a functional version based on the same idea.

    
    def four(el, lst):
        index = 0
        mask = 1 << len(lst).bit_length()
        while mask:
            mask >>= 1
            tmp = index | mask
            if tmp < len(lst) and el >= lst[tmp]:
                index = tmp
            
        return index if lst and el == lst[index] else -1
    
    def five(el, lst):
        def _five(index, mask):
            if mask:
                if index | mask < len(lst) and el >= lst[index | mask]:
                    return _five(index | mask, mask >> 1)
                else:
                    return _five(index, mask >> 1)
            else:
                return index if el == lst[index] else -1
    
        return _five(0, 1 << len(lst).bit_length()) if lst else -1
    
    def nine(el, lst):
        t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i
        m = 1 << (len(lst).bit_length() - 1)
        index = reduce(t, [m >> i for i in range(x+2)], 0)
        return index if el == lst[index] else -1
    
  2. Mike said

    Somehow, I pasted the wrong version of nine(). Here’s the correct version:

    def nine(el, lst):
        t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i
        m = (1 << len(lst).bit_length()) >> 1
        index = reduce(t, [m >> i for i in range(m+2)], 0)
        return index if el == lst[index] else -1
    
  3. matthew said

    @Mike: nice solution, I wish I’d thought of that…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: