Question

How Many Comparisons would be made by binary when searching a list of one million elements in the best and worst case ?

Answer 1

Since only binary is mentioned in the question, I am assuming that question is asking about binary search. If there is any other interpretation, then please let me know in the comment section. I will update my answer accordingly.

The binary search algorithm works only on a sorted input list.
The algorithm compares the middle element of a list with the search key,
Case 1: If mid element == key, it returns mid
Case 2: If mid element < key, it discards left half list, and searches further only in the right half,
updates Low to mid+1
Case 3: If mid element > key, it discards right half list, and searches further only in the left half,
updates High to mid-1

For example: When searchin for key 13, in the list given in the figure, we compare 13 with the mid element 8,
Since mid(8) < 13, we further search only in the right half of the list. By updating Low to Mid + 1, Hence, the low will be at index 5, pointing to element 10.

Since, at each iteration we discard half of the list, In worst case we keep dividing the array until there is only one element left and then we stop. Worst case occurs when the search key is not found in the list.
Since we keep dividing input list of size N, into half until we have list with 1 element, the total number of comparisons in worst case = log₂N+1, where N is the size of input list,

In best case, the binary search finds the element in one comparison,
If the mid element of the original list is the key to be searched, we can find it in just one comparison.

------------------------------------------------------------

Searching a list of one million elements:

N = 1000000

Best case = 1 comparison

Worst case = log₂1000000 + 1 =  21 comparisons

-------------------------------------------------------------------------------------------------------------
Please give a thumbs up if you find this answer helpful.
If it doesn't help, please comment before giving a thumbs down.
Please Do comment if you need any clarification.
I will surely help you.

Thankyou