Question

In the recursive version of binary search each function call reduces the search size by half. Thus in the worst case for a sorted list of length n. The algorithm makes log n calls. Is it possible to make fewer than log n calls?

Group of answer choices

1) Yes, depends on when it finds the element it is looking for

2) No, it will always make log n calls.

Answer 1

OPTION (1) Yes, depends on when it finds the element it is looking for !!

REASON:

In the binary search we will get a sorted array and an element to search for.

We search for the middle element whether that is the required key.

1. If the middle element is Key, return the index of that middle element.
2. Else if the middle element is less than the key, we search in the right half only.
3. Else we search in the LEFT part only.

For example, take n=11 elements.

list = [1,2,3,4,5,6,7,8,9,10,11] are the list of elements.

We want to search for 6. key=6

Now, the middle element is list[(0+11)/2]=list[5]=6

So, we found the key in the first search itself,!! We will stop the search process.

Hence, we just need lest than log₂(11) searches that is 4.

Hence, it depends on when it finds the element it is looking for !!