I have to come up with an algorithm to search a sorted array. Here it is: Code (Text): def binarySearch(inputArray, match): x = -1 start = 0 end = len(inputArray) - 1 while not start == end: midPt = (start + end) / 2 if match < inputArray[midPt]: end = midPt - 1 elif match > inputArray[midPt]: start = midPt + 1 else: return midPt if inputArray[start] == match: x = start return x The code is Python, but I figure anyone can read it without much explination. I have to prove that this algorithm works. I don't know how to do this!! Any help would be appreciated!! Thanks
Maybe you can use strong induction. Show that it works when len(inputArray) = 1, then show that if it works for all arrays of length k or less, then it works for an array of length k+1. Note that if you go through the while loop once, you come back to the top essentially dealing with an array of 1/2 the length, so it would fit in the category of "arrays of length k or less".