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) Output: Index where key was found in s. If not found, it will return -1. binarySearch(s, key) {min = 1 max = n while (min

Solution

(a)
best case would be O(1), when the first iteration will find the key.

(b)
Worst case is O(log n) when the function is unable to find the key.

(c)
1, 5, 7, 8, 20, 22, 78, 90, 101, 202
Key = 101.

Iteration 1:
Mid element = 20

Iteration 2:
Mid element = 90

Iteration 3:
Mid element = 101

So, 3 iterations will be taken to search 101 in the sequence.