note
JavaFan
<blockquote><em>I don't believe it is possible to code a search over sorted data with duplicates that comes even close to be O(log N). Even in theory.</em></blockquote>
You're wrong. You can easily find the smallest index containing your target value by using a condition like:
<code>
return $i if $A[$i] == $target && ($i == 0 || $A[$i-1] < $target);
</code>
instead of the usual
<code>
return $i if $A[$i] == $target;
</code>
And you find the highest index by using:
<code>
return $i if $A[$i] == $target && ($i == $#A || $A[$i+1] > $target);
</code>
It doesn't increase the run time complexity - the worst case of a binary search is when no match is found anyway.
817226
817381