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.

return $i if $A[$i] == $target && ($i == 0 || $A[$i-1] < $target);
[download]

return $i if $A[$i] == $target;
[download]

return $i if $A[$i] == $target && ($i == $#A || $A[$i+1] > $target);
[download]

You can easily find the smallest index containing your target value

How about finding the smallest index that contains a value equal or greater than your target; or highest equal or less?

And how about you post a full sub save all of us trying to recreate your thought?

It doesn't increase the run time complexity

The proof is in the pudding!

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"I'd rather go naked than blow up my ass"

How about finding the smallest index that contains a value equal or greater than your target

sub binary_search {
    my ($str, $a) = @_;
    my $l = 0;
    my $h = @$a;
    while ($l < $h) {
        my $p = int (($l + $h) / 2);
        if ($a->[$p] lt $str) {
            $l = $p + 1;
        }
        else {
            $h = $p;
        }
    }
    $l
}
[download]

update: minor changes to the sub.

How about finding the smallest index that contains a value equal or greater than your target; or highest equal or less?

That doesn't change the complexity.

And how about you post a full sub save all of us trying to recreate your thought?

Too much work to type out all the details.

The proof is in the pudding!

Get any textbook about introductions to algorithms.

superb....

Ok, here is the proof. I programmed the algorithm as described in my first post:

#!/usr/bin/perl
use 5.10.0;
use strict;
use warnings;
use Data::Dumper;

my @data;
for ('aa'..'lz') {
    push @data, ($_) x 7;
}
my $size= scalar(@data);
say 'array size is ',$size,', log2 of ',$size,' is ',int(log($size)/lo
+g(2));

for ('aa','ab','ce','dn','ea','fr','lb') {
    my ($beg,$iterations)= binary_search($_,@data);
    say "Found first '$_' at position $beg after $iterations iteration
+s";
}

#----------------------

sub binary_search {
    my ($search,@data)= @_;
    return(0) if (@data<2);
    my $beg=0; my $end= @data-1;
    my $iter=0;
    while ($beg<$end-1) {
    my $middle= int(($end+$beg)/2);
    if ($data[$middle] lt $search) {
        $beg=$middle; 
    }
    else {
        $end=$middle; 
    }
    $iter++;
    }
    #handle the special case if you are looking for $data[0]
    return($beg,$iter) if ($data[$beg] eq $search);
    return($end,$iter);
}

#output:
array size is 2184, log2 of 2184 is 11
Found first 'aa' at position 0 after 11 iterations
Found first 'ab' at position 7 after 11 iterations
Found first 'ce' at position 392 after 11 iterations
Found first 'dn' at position 637 after 11 iterations
Found first 'ea' at position 728 after 11 iterations
Found first 'fr' at position 1029 after 11 iterations
Found first 'lb' at position 2009 after 11 iterations
[download]

Ok, not a proof in formal language but good enough for us, I hope. As you can see it is a binary search, it takes exactly the number of iterations predicted to find the items. Also it is evident that it finds the first item (see the first two results, and also all following results are dividable by 7)

Regarding the statement: 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. And in practical implementations, it'd be far slower.

Why would the following logic be so much slower in implementation?

• Given: A sorted list containing duplicates
• Given: A target value
• Given: A desired anchor (closest to which endpoint)
• Find: The closest element to the desired anchor that is equal to or $desired_operator than the target value

1. Perform a normal binary search to find the target item
   • If not found, check if $list[$mid] < $val to determine if $mid has to be adjusted by one to meet $anchor/$desired_operator - done
   • If found, proceed to step 2
2. Determine if you are at "right" endpoint of the list of duplicates by checking the $list[$mid - 1] eq $val or $list[$mid + 1] eq $val
   • If yes, done
   • If no, proceed to step 3
3. Check to see if this item is even a duplicate by checking $list[$mid - 1] eq $val or $list[$mid + 1] eq $val - whichever one not done in step 2
   • If not a duplicate - done
   • If a duplicate - proceed to step 4
4. Use the following logic to find the first element in the desired direction that is not a duplicate. For the description, let's say I am trying to find the last element. $min = $mid from previous search and $max = $#list.
   • If $list[$mid] eq $val, $min = $mid
   • If $list[$mid] ne $val, $max = $mid - 1
   • Stop when $max - $min < 2