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
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
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