Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n],...

 

Transcribed Image Text:

Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n], x) 2: left = 1 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: right = n while (right left) mid=left + right-left 2 if x== A[mid] return mid else if x < A[mid] right mid-1 else if > A[mid] left = mid + 1 return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS. Conclude that if x is present in the sorted array A, correctly returns the index of z. (b) Prove by induction that the while loop in lines 4-11 will execute 1+log n times in the worst case. (Hint: observe what happens to the size of the subarray Alleft..right] after each iteration.) Conclude that the running time of the BINARYSEARCH algorithm is (logn). Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n], x) 2: left = 1 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: right = n while (right left) mid=left + right-left 2 if x== A[mid] return mid else if x < A[mid] right mid-1 else if > A[mid] left = mid + 1 return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS. Conclude that if x is present in the sorted array A, correctly returns the index of z. (b) Prove by induction that the while loop in lines 4-11 will execute 1+log n times in the worst case. (Hint: observe what happens to the size of the subarray Alleft..right] after each iteration.) Conclude that the running time of the BINARYSEARCH algorithm is (logn).