Variant of 12.3 Search a sorted array (with duplicates) for entry equal to its index

#1

I wrote several examples but cannot come up with a O(log n) solution when the sorted array can have duplicates.

Any thoughts ?

0 Likes
#2

The O(log n) complexity comes from the fact that you only have to check half of the interval each time. Probably you should also check the ends of the interval, if between those values one that would match the index would fit.

0 Likes