in reply to Re^3: Modified Binary Search

in thread Modified Binary Search

You're wrong. You can easily find the smallest index containing your target value by using a condition like: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.

instead of the usualreturn $i if $A[$i] == $target && ($i == 0 || $A[$i-1] < $target);

And you find the highest index by using:return $i if $A[$i] == $target;

It doesn't increase the run time complexity - the worst case of a binary search is when no match is found anyway.return $i if $A[$i] == $target && ($i == $#A || $A[$i+1] > $target);

In Section
Seekers of Perl Wisdom