in reply to Binary search algorithm
-1 only becomes an alias for $#array
at the point where its value is being used as an index into an array. So
print $array[-1]; is ok, as is
print @array[-1,0,3];.
In this latter case, the -1 is part of a list of indices in the array slice.
However, in print @array[0..-1];,
it isn't yet part of a list, it is an operand to the .. operator that is intended to generate the list of indices, and the .. operator will only generate positive indices, so a null list is generated. Even if .. did generate negative running lists, the result wouldn't be what you wanted betcause
print 0..-1; would result in the list (0,-1) which isn't what is intended at all.
In order for print @array[0..-1];
to DWIM, the complier would have to make a special case of the .. operators context within the subscript of an array which in itself would create another non-orthoganality in that
print @array[0..-1]; would now do something different to
@indices = 0..-1; print @array[@indices];.
It's my guess that this is the main reason why this is done.
Updated from here on.
BTW. One caveat of your implementation of the binary search is that it destroys the input array as a result of the lines
@$aref = @$aref[++$mid..$#$aref]; ... @$aref = @$aref[0..--$mid];
Where you are overwriting the original array (via the reference) with the subsets needed by the binary chop--in this case, literally:).
You can avoid this by creating an anonymous array from the subset when you recurse. This could look something like
sub binary_search { my ($aref, $find) = @_; my $mid; $mid = int $#$aref / 2; return 0 if $find == $aref->[$mid]; return 1 if !$#$aref; if ($find > $aref->[$mid]) { binary_search([ @$aref[++$mid..$#$aref] ], $find); } else { binary_search([ @$aref[0..--$mid] ], $find); } }
Or in a slightly more compact form
sub binary_search { my ($aref, $find) = @_; my $mid = int $#$aref / 2; return 0 unless $#$aref; return 1 if $find == $aref->[$mid]; binary_search( $find < $aref->[$mid] ? [ @$aref[ 0 .. --$mid ] ] : [ @$aref[++$mid .. $#$aref] ] , $find ); }
I also reversed the logic of the return as I would prefer to say
if (binary_search(\@array, $needl) ) { #found it }
to if (binary_search(\@array, $needle)){ #Didn't find it }
but that's just a personal preference.
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re: Re: Binary search algorithm
by mjab (Sexton) on Apr 21, 2003 at 12:49 UTC |