Consider the following binary search algorithm for a sequenc

Consider the following binary search algorithm for a sequence s. input: s (sequence that is sorted), key (value to search in s), n (size of s) Ouput: Index where key was found in s. If not found, it will return -1. binarySearch(s, key) {min = 1 max = n while (min leftarrow max) {mid = floor((min+max)/2) if (s_mid = key) return mid else if (Said

Solution

a) The best case for the algorithm is when the key is the middle element of the sequence.

b) The worst-case for the algorithm is when the key does not exist in the array.

c) Here the key given is 101, the number of elements in sequence is 10. So value of mid:

-> mid wil be 5. mid element is 20, so now min will be 6.

-> mid will be 8, mid element will be 90, so now min will 9.

-> mid will be 9, mid element will be 101. It stops.

The instruction 5 will be executed 3 times.