function binary_search
   (key : in KeyType;
    A   : in ArrayType) return natural is
            low,high, middle : positive;
begin
   low  := A'First;
   high := A'Last;
   while low <= high loop
      middle := (low+high)/2;
      if key < A(middle) then
         high := middle-1;
      elsif
         key > A(middle) then
         low  := middle+1;
      else
         return middle; -- when key found
      end if;
   end loop;
   return 0; -- when key not found
end binary_search;

-----------------------------------------------------

-- well, this is a charming piece of code:

-- This code contrasts in a pleasing way to
-- those unspeakable C or Java hacks where
-- people are forced to struggle with poor
-- indexing from 0 to n-1 instead of 1 to n.
-- This is reasonable in assembly programming
-- but dishonorable in higher order languages.
-- Interestingly it is sometimes leading to
-- that abashing trap where a result of zero
-- means both "not found" and "found at 0",
-- as I observed.

-----------------------------------------------------
-- hint for better readability: 
-- subtype natural  is integer range 0..integer'last;
-- subtype positive is integer range 1..integer'last;
-----------------------------------------------------

-- see also
-- http://www.horstpeterhermann.de/ada_related/ak00504a.txt (nongeneric test)
-- http://www.horstpeterhermann.de/ada_related/ak00505a.txt    (generic test)

-- 20041129 Peter Hermann 20130327ph