Input data of the algorithm: sorted, n-element array A and value v. The following algo- rithm...

   

Transcribed Image Text:

Input data of the algorithm: sorted, n-element array A and value v. The following algo- rithm gives the index p such that v = A[p] or NIL if v A. We assume it was invoked with parameters BINARY SEARCH (A, 1, n, v). BINARYSEARCH(A, p, r, v) 1 if p <r 2 3 4 5 6 7 8 - then q [(p+r-1)/2] if v < A[q] then return BINARYSEARCH(A, p, q, v) else return BINARYSEARCH(A, q + 1,r, v) else if v = A[p] then return p else return NIL Prove that this algorithm makes a logarithmic number of comparisons. Input data of the algorithm: sorted, n-element array A and value v. The following algo- rithm gives the index p such that v = A[p] or NIL if v A. We assume it was invoked with parameters BINARY SEARCH (A, 1, n, v). BINARYSEARCH(A, p, r, v) 1 if p <r 2 3 4 5 6 7 8 - then q [(p+r-1)/2] if v < A[q] then return BINARYSEARCH(A, p, q, v) else return BINARYSEARCH(A, q + 1,r, v) else if v = A[p] then return p else return NIL Prove that this algorithm makes a logarithmic number of comparisons.

Answer rating: 100% (QA)

What youve provided is a classic binary search algorithm T... View the full answer