japhy
Enthusiast
/ Moderator
Dec 18, 2000, 9:43 PM
Post #4 of 6
(2616 views)

Hmm, I wasn't happy with the solution we came up with. Our solutions are both O(n/2)  that's the average case, at least. It can be as good as O(1) (if the first element is not 1), or as bad as O(n) if all elements are there, and we just need to add the next in sequence. (This value n represents the size of the array.) So I came up with a binarytree approach, which provides a constant runtime of O(log n). Here's the code:
@a = (1,2,3,4,7,8,9,14); $to_add = find_missing(\@a); sub find_missing { 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][$p1] + 1; } It works by continually splitting the array in half until it finds the lowest misplaced value. Then, it adds one the element BEFORE that misplaced value. If that value happens to be the first element in the array, the function returns 1 automatically. This method is efficient, and runs in O(log n) time all the time. While this proves somewhat poor for a huge array with a first element of something other than 1, it is a good general solution. Jeff "japhy" Pinyan  accomplished hacker, teacher, lecturer, and author
