function search( key : typekey; var r : dataarray ) : integer;
     var i : integer;
         tempr : datarecord;

     begin
     i := 1;
     while ( i<n ) and ( r[i].k <> key ) do i := i+1;

     if key = r[i].k then
          begin
          if i>1 then
               begin
               {*** Transpose with predecessor ***}
               tempr := r[i];
               r[i] := r[i-1];
               r[i-1] := tempr;
               i := i-1
               end;
          search := i    {*** found(r[i]) ***}
          end
     else search := -1;  {*** notfound(key) ***}
     end;