I've been writing more Java lately and reading about Scala to the deficit of my Python. So I figured i'd take a little time this morning to do a code kata in Python. I may implement it in Ruby as well but that remains to be seen. I'm not a huge Ruby fan.
Keep in mind this is probably not my best implementations of these. I could spend some more time making them better, but I think they served their purpose anyhow. It's not like i'd ever use these functions as many people smarter than i have already implemented advanced collections functionality in pretty much every language.
Recursive Method
def chop(lookingfor, array):
l = len(array)
if l == 0:
return -1
elif l == 1:
return 0 if array[0] == lookingfor else -1
midpoint = l/2
if array[midpoint] == lookingfor:
return midpoint
if array[midpoint] < lookingfor:
x = chop(lookingfor, array[midpoint:])
return -1 if x == -1 else midpoint + x
else:
x = chop(lookingfor, array[:midpoint])
return -1 if x == -1 else x
Non Recursive Method
def chop(lookingfor, array):
low = 0
high = len(array)
while low < high:
m = (low + high) / 2
if array[m] == lookingfor:
return m
elif m == low:
break
elif array[m] > lookingfor:
high = m
elif array[m] < lookingfor:
low = m
return -1
Rest of the Python Files
def main():
import doctest
doctest.testmod()
if __name__ == '__main__':
main()
Doctest “Tests”
"""
>>> chop(3, [])
-1
>>> chop(3, [1])
-1
>>> chop(1, [1])
0
>>> chop(1, [1, 3, 5])
0
>>> chop(3, [1, 3, 5])
1
>>> chop(5, [1, 3, 5])
2
>>> chop(0, [1, 3, 5])
-1
>>> chop(2, [1, 3, 5])
-1
>>> chop(4, [1, 3, 5])
-1
>>> chop(6, [1, 3, 5])
-1
>>> chop(1, [1, 3, 5, 7])
0
>>> chop(3, [1, 3, 5, 7])
1
>>> chop(5, [1, 3, 5, 7])
2
>>> chop(7, [1, 3, 5, 7])
3
>>> chop(0, [1, 3, 5, 7])
-1
>>> chop(2, [1, 3, 5, 7])
-1
>>> chop(4, [1, 3, 5, 7])
-1
>>> chop(6, [1, 3, 5, 7])
-1
>>> chop(8, [1, 3, 5, 7])
-1
>>> chop(5, range(1, 10000))
4
>>> chop(498, range(1, 1000))
497
"""
Comments