With respect to an array containing a lot of duplicate elements, is there any operations to improve the performance of normal binary search?

Question

With respect to an array containing a lot of duplicate elements, is there any operations to improve the performance of normal binary search?

Answer 1

You can create two arrays. One for values, and the other for repetitions. Then, you can search the values array using binary search.

Answer 2

AraK's answer is 'the only' answer. In general you can't improve worst-case performance on any array with duplicates. Let's say your duplicates tend to concentrate on the end of the array. Now you're looking for an element towards the beginning: your search will have to run as usual.

If you know that duplicates tend to appear on one side more often, you can skew the splitting to improve average performance. If they appear towards the end, e.g., you can do the first split at 1/3 instead of 1/2.