program lineal(input,output);
uses crt,lpri;

const
   TALLAMAX=2000;    (* maxima talla considerada *)
   TALLAMIN=100;      (* talla inicial *)
   TALLAPAS=100;     (* paso de una talla a la siguiente *)
   INST=1;        (* INST*n n§ de instancias para cada talla *)


function Binaria(var A:vector;x:integer;n:index):integer;
var
   i,j:integer;
   central:integer;
   salida: integer;
begin
   i:=1;
   j:=n;
   salida:=0;
   repeat
      central:=(i+j) div 2;
      if x=A[central] then
      begin
           i:=j+1;
           salida:=central;
      end
      else
      begin
         if x<A[central] then j:=central-1
         else
            i:=central+1;
      end;
   until (i>j);
   Binaria:=salida;
end;


   (******************************************************************)
   (*         procedimiento buslin_cost                              *)
   (*         entradas:                                              *)
   (*                  vector con los elementos                      *)
   (*                  numero de elementos                           *)
   (******************************************************************)

function CalculaMedia(var A:vector;n:integer):real;
var
   i, j, x  : integer;
   ins, pos : integer;
   t        : real;

begin

   ins:=trunc(INST*n);
   genera_perm_ord(A,n);
   ResetClock;
   for j:=1 to ins do
   begin
        x:=aleat(0,n-1);
        pos:=Binaria(A,x,n);
   end;
   t:=ClockSec;
   CalculaMedia:=t/ins;
end;


var
   i:integer;
   A:vector;
   n:integer;
   fcost:string[50];

BEGIN {lineal.pas}
   writeln('Nombre del fichero de resultados:   ');
   readln(fcost);
   assign(output,fcost);
   rewrite(output);
   aleat_init;
   InstallClock(10);
   n:=TALLAMIN;
   while (n<=TALLAMAX) do
   begin
      writeln(n,'  ',CalculaMedia(A,n):4:8);
      n:=n+TALLAPAS;
   end;
   UnInstallClock;
   (* Al final escribimos en pantalla *)
   assign(output,''); rewrite(output);
   write('OK'); readln;
END.