Given an ordered list of numbers starting at 1, this code returns the earliest missing number. It runs in O(log n) time due to a binary scan, instead of the possible O(n) time a linear scan would impose.
# $X = missing_n(\@sorted_numbers);

sub missing_n {
  my ($L, $U) = (0, $#{ $_[0] });
  my $p = $L + int(($U - $L)/2);

  return 1 if $_[0][0] != 1;
  return $_[0][-1] + 1 if $_[0][-1] == @{ $_[0] };

  until ($L == $U) {
    if ($_[0][$p] == $p+1) { $L = $p + 1 }
    else { $U = $p }
    $p = $L + int(($U - $L)/2);
  }

  return $_[0][$p-1] + 1;
}

[download]

Replies are listed 'Best First'.
Re: first missing number
by repson (Chaplain) on Dec 19, 2000 at 13:04 UTC
    Just one question...where did you initialize $_?
    Or shouldn't the places where you do $_->[$p] be $_[0][$p] unless you have an invisible ($_)=@_; at the beginning?

    Interesting algorithm, I'm sure I would be useful for something...someday, I just can't think what :)

[reply]
[d/l]
[select]
      Oops, my apologies. I wrote it as passing the array, and then I realized it'd be faster to pass an array ref. And I misadjusted.

      japhy -- Perl and Regex Hacker
[reply]
[reply]
Re: first missing number
by merlyn (Sage) on Dec 19, 2000 at 11:15 UTC
    I'm not sure this saves any time. I didn't follow the algorithm, but if I understand the problem correctly, you still need to check $array[0] through $array[$n] regardless, if you're going to declare $n+1 as a first missing number. So why probe anything beyond that?

    -- Randal L. Schwartz, Perl hacker

[reply]
[d/l]
[select]
      I think the problem description should be made a little more specific; the array must contain only positive integers, and must have no duplicates. With that in mind, you don't have to check $array[0] through $array[$n]. If $array[$n] == $n+1 -- e.g., if $array[25] is 26 -- then you know that there are no missing numbers in @array[0..$n].
[reply]
[d/l]
[select]
        Ahh... the word "sorted" was missing when I first looked at it. OK, then yes, you can determine it with O(log n) probes. Silly me. {grin}

        -- Randal L. Schwartz, Perl hacker

[reply]

Back to Cool Uses for Perl