First, I want to say thank you to everyone who offered their critiques and advice.
Not only did I learn a lot about binary search, I learned a lot about how to write better Python code.
def binary_search(keys, target, start = 0, end = None):
end = end if end is not None else len(keys) - 1
if end < start:
return -1
mp = start + (end - start) // 2
if target == keys[mp]:
return mp
elif target < keys[mp]:
return binary_search(keys, target, start = start, end = mp - 1)
else:
return binary_search(keys, target, start = mp + 1, end = end)
def left_finder(keys, target, start = 0, end = None):
end = end if end is not None else len(keys) - 1
if end < start:
return -1
mp = start + (end - start) / /2
if ((mp == 0 or keys[mp - 1] < target) and keys[mp] == target):
return mp
elif target <= keys[mp]:
return left_finder(keys, target, start = start, end = mp - 1)
else:
return left_finder(keys, target, start = mp + 1, end = end)
def right_finder(keys, target, start = 0, end = None):
end = end if end is not None else len(keys) - 1
if end < start:
return -1
mp = start + (end-start) // 2
if ((mp == len(keys) - 1 or target < keys[mp + 1]) and keys[mp] == target):
return mp
elif target < keys[mp]:
return right_finder(keys, target, start = start, end = mp - 1)
else:
return right_finder(keys, target, start = mp + 1, end = end)
def duplicate_binary_search(keys, target):
left, right = left_finder(keys, target), right_finder(keys, target)
assert left <= right
assert (left == -1) == (right == -1)
return [] if left == -1 else list(range(left, right + 1))
