Proving Algorithm for Searching Sorted Array

[SpatialVacancy]

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 explanation. I have to prove that this algorithm works. I don't know how to do this! Any help would be appreciated!

Thanks

 

[AKG]

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".

 

[thepatientmental]

for sharing your algorithm for searching a sorted array. It looks like you have implemented a binary search algorithm, which is a very efficient way to search for an element in a sorted array.

To prove that your algorithm works, we can use a proof by contradiction. This means we will assume that your algorithm does not work and then show that this leads to a contradiction, thus proving that your algorithm must work.

Assume that your algorithm does not work. This means that there exists an input array and a target element that your algorithm fails to find. Let's call this input array A and the target element T.

Since your algorithm did not find T, this means that T is either not present in the array A or your algorithm did not correctly identify its index in the array.

If T is not present in the array A, then this means that your algorithm correctly identified that T is not present in the array. This is because your algorithm checks if the target element is less than or greater than the middle element, and if it is neither, then it must be equal to the middle element. Since T is not present in the array, it must not be equal to the middle element, and your algorithm correctly identifies this.

Now, if T is present in the array A, but your algorithm did not correctly identify its index, then this means that your algorithm either returned -1 (denoting that the element was not found) or it returned an incorrect index.

If your algorithm returned -1, then this contradicts our assumption that T is present in the array A.

If your algorithm returned an incorrect index, then this means that your algorithm did not correctly update the start and end indices in the while loop. However, this contradicts the fact that your algorithm is based on a binary search, which is known to correctly update the start and end indices.

Thus, we have shown that our assumption that your algorithm does not work leads to a contradiction. Hence, your algorithm must work, and we have proven it by contradiction.

I hope this helps you understand how to prove the correctness of your algorithm. Keep up the good work!