Prove an Algorithm


by SpatialVacancy
Tags: algorithm, prove
SpatialVacancy
SpatialVacancy is offline
#1
Apr13-05, 05:10 PM
P: 24
I have to come up with an algorithm to search a sorted array. Here it is:

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
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
AKG
AKG is offline
#2
Apr13-05, 05:35 PM
Sci Advisor
HW Helper
P: 2,589
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".


Register to reply

Related Discussions
DFS algorithm Programming & Computer Science 2
RSA Algorithm Computing & Technology 2
Prove the algorithm for LCM Set Theory, Logic, Probability, Statistics 7
ln(x) algorithm General Math 2