I have written this function to perform a binary search on an array, given begin/end indices and a value to look for in the supplied array:
def binarySearch(array, beginIndex, endIndex, value): while (beginIndex < endIndex): mid = (beginIndex + endIndex) / 2 if array[mid] < value: beginIndex = mid + 1 elif array[mid] > value: endIndex = mid - 1 else: #equal return mid if array[beginIndex] == value: return beginIndex else: return -1
Test cases / output:
print binarySearch([2,3], 0, 1, 2) 0 print binarySearch([2,3], 0, 1, 3) 1 print binarySearch([2,3], 0, 1, -1) -1 print binarySearch([2,3,3,3,4,5], 0, 5, 3) 2
So it works as intended. I'm interested in feedback mostly from a functional perspective, but I'm open to anything else that might catch your eye.