CODEWITHSUNDEEP
time-complexitybinary-search
Ankita
Ankita

Reputation: 33

What would be the binary search complexity to find second largest number in array

Can someone explain how to calculate the binary search complexity to find second largest number in array.

Upvotes: 1

Views: 201

Answers (3)

Sanket Patel
Sanket Patel

Reputation: 259

One way to do it in python efficiently can be to convert list[which allows duplicates] to set[which does not allow duplicates] almost in O(1) time and then fetching item at index[-2] again in O(1) time, assuming that as it is binary search list would be sorted in ascending order.

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66459

Binary search for an element with any given property is always logarithmic, provided that you can determine in constant time whether that property holds.

If the array can’t contain duplicates, you don’t need a binary search and the complexity is constant.

Upvotes: 0

Ojasvi Monga
Ojasvi Monga

Reputation: 5139

Binary search is done on a sorted array. If you already have a sorted array, why do you need to do anything at all?

The second to last number in the array (sorted in ascending order) would be the second largest number.(O(1))

If the array contains duplicates:

For example, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,... }

The time complexity would be O(log n) where n is the number of elements in the array.

The smallest number is the one at index 0 (call it x), now you can use binary search to find the array bounds within which all elements are equal to x. The immediate neighbour outside these bounds would be the second largest number in the array.

If you are using C++, you can use this method to get the upper_bound.

Upvotes: 1

Related Questions