Mega Code Archive
Binary search of an array
<![CDATA[
for ( $i = 0; $i < 15; ++$i ) {
$array[ $i ] = 2 * $i;
}
print "Enter an integer search key: ";
chomp ( $searchKey = <STDIN> );
print "\n";
for ( $i = 0; $i < @array; ++$i ) {
print $i < 10 ? " $i " : " $i ";
}
print "\n", "-" x ( 4 * @array ), "\n";
$found = 0; # search while !$found
$lowIndex = 0; # start index for search
$highIndex = $#array; # end index for search
while ( $lowIndex <= $highIndex && !$found ) {
$middleIndex = ( $lowIndex + $highIndex ) / 2;
for ( $i = 0; $i < @array; ++$i ) {
if ( $i < $lowIndex || $i > $highIndex ) {
print " ";
}
elsif ( $i == $middleIndex ) {
print $array[ $i ] < 10 ? " $array[ $i ]*" : " $array[ $i ]*";
}
else {
print $array[ $i ] < 10 ? " $array[ $i ] " : " $array[ $i ] ";
}
}
print "\n";
if ( $searchKey == $array[ $middleIndex ] ) { # match
$index = $middleIndex;
$found = 1;
}
elsif ( $searchKey < $array[ $middleIndex ] ) {
$highIndex = $middleIndex - 1; # search low end of array
}
else {
$lowIndex = $middleIndex + 1; # search high end of array
}
}
# display results
if ( $found ) { # $found == 1
print "\nFound $searchKey at subscript $index \n";
}
else { # $found == 0
print "\n$searchKey not found \n";
}
]]>