1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...