For Kata Two — Karate Chop I’m supposed to implement a binary search five different ways. PragDave suggests starting of with the “traditional iterative approach.” My first thought was, “what the heck is that?” It’s been a while since my intro. to data structures and algorithms class. I figure it has something to do with a while loop and checking the middle index in the array being searched, so that’s where I started:

def chopOne(value, list):
index = (len(list) - 1) / 2

while index > -1:
if list[index] == value:
return index
elif value > list[index]:
index = (index + len(list) - 1) / 2
elif value < list[index]:
index = index / 2

return -1

Well, that didn’t work. I got into an infinite loop. As I thought about it, I remembered I had to keep track of the upper and lower bounds that I had already checked. So this got me:

def chopOne(value, list):
upper = len(list) - 1
lower = 0
index = (upper + lower) / 2

while index > -1 and upper >= lower:
if list[index] == value:
return index
elif value > list[index]:
lower = index + 1
elif value < list[index]:
upper = index - 1
index = (upper + lower) / 2

return -1

That worked! Next, time I’ll use recursion to implement the binary search.