CODEWITHSUNDEEP
time-complexitycomplexity-theorybinary-search
BlackPearl
BlackPearl

Reputation: 95

Binary Search: Number of comparisons in the worst case

I am trying to figure out the number of comparisons that binary search does on an array of a given size in the worst case.

Let's say there is an array A with 123,456 elements (or any other number). Binary search is applied to find some element E. The comparison is to determine whether A[i] = E. How many times would this comparison be executed in the worst case?

According to this post, the number of worst case comparisons is 2logn+1. Result: 50

According to this post, the max. number of binary search comparisons is log2(n+1). Result: 25

According to this post, the number of comparisons is 2logn-1. Result: 50

I am confused by the different answers. Can anyone tell me which one is correct and how I can determine the maximum number of comparisons in the worst case?

Upvotes: 1

Views: 698

Answers (1)

HEKTO
HEKTO

Reputation: 4191

According to this Wiki page:

In the worst case, binary search makes floor(log2(n)+1) iterations of the comparison loop, where the floor notation denotes the floor function that yields the greatest integer less than or equal to the argument, and log2 is the binary logarithm. This is because the worst case is reached when the search reaches the deepest level of the tree, and there are always floor(log2(n)+1) levels in the tree for any binary search.

Also, it's not enough to consider only comparisons A[i] = E. The binary search also includes comparisons E <= A[mid], where the mid is the midpoint of the index interval.

Upvotes: 1

Related Questions