Recall the algorithm for binary search which finds the index in a sorted array of integers...

Transcribed Image Text:

Recall the algorithm for binary search which finds the index in a sorted array of integers A for some item z (we assume z exists in A). def binarysearch (x, A, 1-0, r-A. length-1): while True: m= (1+r)/2; if x= A[m]: return m if x < A[m]: else: r = m-1 Algorithm 2: Binary Search 1 = m+1 Give the loop invariant for binary search's proof of correctness. Recall the algorithm for binary search which finds the index in a sorted array of integers A for some item z (we assume z exists in A). def binarysearch (x, A, 1-0, r-A. length-1): while True: m= (1+r)/2; if x= A[m]: return m if x < A[m]: else: r = m-1 Algorithm 2: Binary Search 1 = m+1 Give the loop invariant for binary search's proof of correctness.

Answer rating: 100% (QA)

The loop invariant for the binary search algorithm is At the beginning of each iteration the subarra... View the full answer