-- Busqueda dicotomica en ADA

WITH Ada.Text_IO;
WITH Ada.Float_Text_IO;
WITH Ada.Integer_Text_IO;
WITH Ada.Numerics.Discrete_Random;
WITH Ada.Real_Time;

USE  Ada.Text_IO;
USE  Ada.Integer_Text_IO;
USE  Ada.Real_Time;

PROCEDURE bin IS

   N:CONSTANT Positive:=2000;
   SUBTYPE NEl IS Natural RANGE 0..N;
   TYPE Vec IS ARRAY(NEl) OF INTEGER;
   PACKAGE Random2000 IS NEW Ada.Numerics.Discrete_Random
      (Result_Subtype => NEl);

   PACKAGE dur_io IS NEW Ada.Text_IO.Fixed_IO(Duration); 

   G: Random2000.Generator;
   

PROCEDURE InVec(V : OUT Vec) IS
BEGIN
   FOR i IN NEl LOOP
      V(i):=i;
   END LOOP;
END InVec;

FUNCTION Binaria(V:IN Vec; busq: NEl; talla: NEl) RETURN NEl IS

   i:NEl;
   j:NEl;
   c:NEl;
   res:NEl;  
BEGIN
   i:=1;
   j:=talla;
   res:=0;
   LOOP
      c:=(i+j)/2;
      IF V(c)=busq THEN
         i:=j+1;
         res:=c;
         ELSIF busq<V(c) THEN
            j:=c-1;
         ELSE
            i:=c+1;
      END IF;
      EXIT WHEN (i>j);
   END LOOP;
   RETURN res;
END Binaria;

FUNCTION CalculaMedia(V:IN Vec; talla:IN NEl) RETURN Duration IS
   xel:NEl;
   pos:NEl;
   tiempo1,tiempo2:Time;
   d:Duration;
   t:Time_Span;
BEGIN
   Random2000.Reset(G);
   d:=To_Duration(Time_Span_Zero);
   FOR i IN 1..20 LOOP
      xel:=Random2000.Random(G) mod talla;
      tiempo1:=Clock;
      FOR m IN 1..100000 LOOP
         pos:=Binaria(V,xel,talla);
      END LOOP;
      tiempo2:=Clock;
      t:=tiempo2-tiempo1;
      d:=d+To_Duration(t);
   END LOOP;
   RETURN (d/(100000*20));
END CalculaMedia;

talla:NEl;
V:Vec;
du:Duration;
fd:Ada.Text_IO.File_Type;

BEGIN
   InVec(V);
   talla:=100;
   Create(fd,OUT_FILE,"Salida.dat");
   LOOP
      put(talla);
      New_Line;
      du:=CalculaMedia(V,talla);
      put(fd,talla);
      put(fd,"    ");
      dur_io.Put(fd,du);
      New_Line(fd);
      EXIT WHEN talla=2000;
      talla:=talla+100;
   END LOOP;
   Close(fd);
END Bin;