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;