CODEWITHSUNDEEP
algorithmbinary-search
weikangduan
weikangduan

Reputation: 57

binary search with duplicate elements in the array

I was wondering how do we handle duplicate elements in an array using binary search. For instance, I have an array like 1 1 1 2 2 3 3 . And I am interested in looking for the last occurrence of 2.

According to a post I read before, we can first use binary search to find 2, and then scan through the adjacent elements. This takes about o(log(n)+k). So the worst case is when k = n. Then it takes O(n) time. Is there any way to improve the performance of worst time. Thanks.

Upvotes: 1

Views: 1857

Answers (2)

user3386109
user3386109

Reputation: 34829

Do a binary search for 2.5. In other words, if the value you're searching for is N, then your code should treat N like it's too small, and N+1 like it's too large. The main difference in the algorithm is that it can't get lucky and terminate early (when it finds the value). It has to run all the way till the end, when the high and low indexes are equal. At that point, the index you seek should be no more than 1 away from the final high/low index.

Upvotes: 1

Cort Ammon
Cort Ammon

Reputation: 10863

The easiest approach would be to do an upper-bound binary search. This is exactly like the binary search you mention, except instead of trying to find the first instance of a number, it first the first instance of a number which is greater than the one provided. The difference between them is little more than switching a < to a <=.

Once you find the first instance of a number which is greater than yours, step back one index, and look at the value there. If it's a 2, then you found the last 2. If it's anything else, then there were no 2's in the array.

Upvotes: 1

Related Questions