Question

The maximum number of searches required by the binary search algorithm to search an ordered list of n items, where n is a power of 2, what is the time complexity?

Answer 1

Let us consider n=1000..

and in worst case scenario we are searching for the element stored in the o^th index then it will search for 10 times to reach it.

As 1000/2=500.

500/2=250.

250/2=125.

125/2=62.

62/2=31.

31/2=15.

15/2=7.

7/2=3.

3/2=1.

1/2=0.

There by if there are n elements exists in a sorted array,then maximum number of comparisons may require is log₂n.

Explanation:

Binary Search Algorithm is known as half interval search or the logarithmic search which finds the position of the target value within a sorted array only.

It starts with the middle element of the array and if the target value matches with the middle element then it is the best case possible in O(1).

If it does not match with the current middle value then it compares with the value stored in the middle index.

If the value in the middle index is greater than the target value then the search goes to the right side of the array and if the value in the middle index is lesser than the target value then the search goes to the left side of the array.

Algorithm

1. Set L to 0 R to n-1

2. If L>R,then search terminates as unsuccesful.

3.Set m ( the position of the middle element) to the floor(largest prev integer) to (L+R)/2

4. If target=A_m ,the search is done.

5. If target>A_m ,set L to m+1 and go to step 2

6. If target<A_m set L to m-1 and go to step 2

Time Complexity

T(n)=T(n/2)+1 if n>1

T(n)=1 if n=1

There by T(n)=O(log₂n)