CODEWITHSUNDEEP
time-complexitybinary-search
XDXDXD
XDXDXD

Reputation: 69

How to calculate the worst case time for binary search for a key that appears twice in the sorted array?

What would be the worst case time complexity for finding a key that appears twice in the sorted array using binary search? I know that the worst case time complexity for binary search on a sorted array is O(log n). So, in the case that the key appears more than once the time complexity should be lesser than O(log n). However, I am not sure how to calculate this.

Upvotes: 2

Views: 1174

Answers (1)

abc
abc

Reputation: 11929

In the worst case the binary search needs to perform ⌊log_2(n) + 1⌋ iterations to find the element or to conclude that the element is not in the array.

By having a duplicate you might just need one step less.
For instance, suppose your duplicate elements appear in the first and second indices of the array (same if they are in the last and one before the last). In such a case you would have ⌊log_2(n)⌋ comparisons, thus, still O(log(n)) as a worst case time complexity.

Upvotes: 2

Related Questions