## Prove an Algorithm

I have to come up with an algorithm to search a sorted array. Here it is:

Code:
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
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 Recognitions: Homework Help Science Advisor 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".