PROCEDURE Binary_Search_Generic (List   : IN ListType;
                               Target  : IN KeyType;
                               Location: OUT IndexType;
                               Found   : OUT Boolean) IS
------------------------------------------------------------------
--| Body of Generic Binary Search Procedure
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: October 1995                                     
------------------------------------------------------------------
 
  Middle : IndexType;      -- the subscript of the middle element
  Success: Boolean;
  Left   : IndexType;
  Right  : IndexType;
 
BEGIN -- Binary_Search_Generic
  
  Left := List'First;
  Right := List'Last;
  Success:= False;

  IF Target = KeyOf(List(Left)) THEN
    Found := True;
    Location := Left;
  ELSIF Target < KeyOf(List(Left)) THEN -- Target goes in pos. 1
    Found := False;
    Location := Left;
  ELSIF Target = KeyOf(List(Right)) THEN
    Found := True;
    Location := Right;
  ELSIF NOT (Target < KeyOf(List(Right))) THEN -- Target beyond end
    Found := False;
    Location := IndexType'Succ(Right);
  ELSE
    WHILE (Left <= Right) AND (NOT Success) LOOP

      Middle := IndexType'Val((IndexType'Pos(Left)
                             + IndexType'Pos(Right)) / 2);
      IF Target = KeyOf(List(Middle)) THEN
        Success := True;
      ELSIF Target < KeyOf(List(Middle)) THEN
        Right := IndexType'Pred(Middle);    -- search lower subarray   
      ELSE
        Left := IndexType'Succ(Middle);     -- search upper subarray
      END IF;

    END LOOP;
 
    IF (NOT Success) AND KeyOf(List(Middle)) < Target THEN
      Location := IndexType'Succ(Middle);
    ELSE
      Location := Middle;
    END IF;

    Found := Success;

  END IF;

END Binary_Search_Generic;