Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove an Algorithm

  1. Apr 13, 2005 #1
    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
     
  2. jcsd
  3. Apr 13, 2005 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Prove an Algorithm
  1. Prove that (Replies: 2)

  2. Prove This! (Replies: 26)

  3. Division algorithm (Replies: 5)

  4. Prove this (Replies: 1)

Loading...