Search sorted array for entry equal to its index - variant 1

#1

[12.2 variant 1 in EPIJ v 1.6.1]
Variant 1 modifies the original problem by allowing the array to contain duplicates.
Is a O(log n) solution possible for this variant? I have a solution, but I think it’s O(n) in the worst case, O(log n) in the average case.

0 Likes

#2

I think it is impossible to solve this problem in O(logn) in worst case.

0 Likes

#3

Then I’m probably on the right track. Cool. Thanks!

0 Likes