3.4 Exercises Exercise 3.1. Consider Worked exercise 2.2. Prove the correctness

Question

3.4 Exercises Exercise 3.1. Consider Worked exercise 2.2. Prove the correctness of your algorithm by using mathematical induction. Worked Exercise 2.2. You are given a sorted array S1,..., n] ofn (distinct) numbers, i.e., the numbers in the array are arranged in increasing order: Give a recursive algorithm to search for a given element (say z) in the array Ifs is present in the array, the algorithm should return the index of the position where it is present, otherwise it should return o. Your algorithm should take O(log n) comparisons. Give pseudocode of your algorithm and argue that your algorithm indeed takes O(log n) comparisons (in the worst case). The algorithm is very similar to the binary search algorithm for the Square root problem. But care has to be taken to avoid "off-by-one type errors (in setting the termination condition and the low and high values.). Algorithm 5 Algorithm Binary-Search(S,nSorted array SIi,..., n and an element r. Output: If z is in S, then i such that Si-z or output "null' 1: low 1 // Low value of guess 2: high = n // High value ofguess 3: while low S high do 4: mid (low +high)/2 6: Output mid and STOP /I this is the answer 7: else if Slmid

Explanation / Answer

Using mathematical induction,

for n=1,

          low = high =mid =1

         if x = S[mid] is in between low and high, then BinarySearch(S,x) is again called.

         It must be the case that x = S[mid], then function will return mid, an index of array S.

suppose, BinarySearch(S,x) works for n<=k then we have to prove that it also works for

n=k+1.

If x = S[mid], clearly the function works correctly.

If x < S[mid], then

         if low = 1 and high = n then "mid" must be in between low and high.

         and mid = (low + high-1)/2 , if (n is even) and mid = (low + high )/2, if(n is odd)

         for the next recursive call, n must be (mid - low - 1)

        i.e. n= floor((low+high)/2] - low -1     

        if (low + high) is even, then n= (high - low)/2 -1 which must be less that k+1 = (high - low).

        if(low + high ) is odd, then n = (high - low -1)/2 -1 which is also less that k+1 = (high - low).

        So recursive call must be in range 1 to k+1. i.e. the hypothesis is also true for n = k+1.

if x > S[mid], then

       we have to show that (high - (mid +1))<=k+1,

       since, mid = floor((high + low)/2)

       then,   high - floor((high+low)/2) -1 = (high -low)/2 - 1 , if(low + high) is even.

                                                         = (high - low)/2 -1/2 , if (low + high) is odd.

                In both cases, high - floor((high + low)/2) -1 is less than (high - low) = k+1 >0

     So, In this case, It is also true for n = k+1

    Since, In all cases, induction works perfectly. so we can say, above given algorithm,

    BinarySearch(S,x) is correct.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.