#!/usr/bin/perl
# Fig. 4.14: fig04_14.pl
# Binary search of an array.

# populate @array with the even integers from 0 to 28
for ( $i = 0; $i < 15; ++$i ) {
   $array[ $i ] = 2 * $i;   
}

# prompt the user for a search key
print "Enter an integer search key: ";
chomp ( $searchKey = <STDIN> );

# display header string for output
print "\n";                  # output a blank line

for ( $i = 0; $i < @array; ++$i ) {
   print $i < 10 ? "  $i " : " $i ";
}

print "\n", "-" x ( 4 * @array ), "\n";

# perform a binary search
$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;
   
   # lines 32 through 46 are for output purposes only  
   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";
   # back to binary searching
   
   # the following if/elsif/else determines if $searchKey
   # has been found
   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";
}



###########################################################################
#  (C) Copyright 2001 by Deitel & Associates, Inc. and Prentice Hall.     #
#  All Rights Reserved.                                                   #
#                                                                         #
#  DISCLAIMER: The authors and publisher of this book have used their     #
#  best efforts in preparing the book. These efforts include the          #
#  development, research, and testing of the theories and programs        #
#  to determine their effectiveness. The authors and publisher make       #
#  no warranty of any kind, expressed or implied, with regard to these    #
#  programs or to the documentation contained in these books. The authors #
#  and publisher shall not be liable in any event for incidental or       #
#  consequential damages in connection with, or arising out of, the       #
#  furnishing, performance, or use of these programs.                     #
###########################################################################