Busqueda en memoria por mas cercano

[jars]

Hola amigos,
Tengo lo siguiente: Necesito una estructura en la que pueda almacenar los siguientes datos:
TimeOffset :LongWord; (clave)
prevTimeOffset :LongWord; (datos)
PositionOffset :LongWord; (datos)

La clave seria TimeOffset.
El problema se centra en la búsqueda ya que el valor a buscar (x) no es precisamente el almacenado sino uno que sea x > a y x < b.
Ejemplo:

Elemento clave datos
1 2183 0 0E
2 4447 2183 8EBE
3 6720 4447 11DC2
4 8983 6720 1AD26
... ... .... .....

El dato a buscar pej. es 5300, tengo que encontrar la clave 4447, (x > elemento 2 y x < elemento 3) se entiende?
La cantidad de elementos es variable y puede ser bastante grande por eso pensé en alguna tabla hash porque tengo entendido que son las mas rápidas aunque nunca las he usado y no se como hacerlo.

Espero haberme explicado bien y cualquier ayuda será bienvenida.

Gracias
Jorge

[ecfisa]

Hola Jorge.

El dato a buscar pej. es 5300, tengo que encontrar la clave 4447, (x > elemento 2 y x < elemento 3) se entiende?

En base a lo que escribiste, el valor que debe obtenerse, es el próximo menor, a la clave a buscar.

Suponiendo que la clave a buscar 'TimeOffset' esté ordenada, para buscar utilizaría una busqueda por dicotomía binaria que es la más rápida, siendo su número de comparaciones de Log2(N). (aprox. 20 comparaciones para 1000000 de elementos). Por último, para simplificar el uso y almacenamiento de los valores; un arreglo dinámico.

Te hice un ejemplo simple, muestra también los valores generados en un memo para que puedas verificarlo.

Código Delphi [-]
...
type
  Registro = record
    TimeOffset: LongWord;
    PrevTimeOffset: LongWord;
    PositionTimeOffset: LongWord;
  end;

  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    Vec: array of Registro;
    procedure MostrarArreglo;
    function BuscarDB(Valor: LongWord): LongWord;
  public
  end;

var
  Form1: TForm1;

implementation {$R *.dfm}

const
   MAX = 100;

{ Llenar el arreglo }
procedure TForm1.FormCreate(Sender: TObject);
var
  i,c: integer;
begin
  SetLength(Vec, MAX);
  c:= 0;
  for i:= Low(Vec) to High(Vec) do
  begin
    Vec[i].TimeOffset:= c;
    Vec[i].PrevTimeOffset:= c+50;
    Vec[i].PositionTimeOffset:= i;
    Inc(c,100);
  end;
 
end;

{ Mostrar en Memo }
procedure TForm1.MostrarArreglo;
var
  i: Integer;
begin
  Memo1.Clear;
  for i:= Low(Vec) to High(Vec) do
    Memo1.Lines.Add(Format('%4d %4d %4d',
    [Vec[i].PositionTimeOffset, Vec[i].TimeOffset, Vec[i].PrevTimeOffset]));
end;

{ Busqueda binaria }
function TForm1.BuscarDB(Valor: LongWord): LongWord;
var
  Pri, Ult, Med : LongWord;
  Esta : boolean;
begin
   Pri := Low(Vec);
   Ult := High(Vec);
   Esta := False;
   while (Pri <= Ult) and not Esta do
   begin
      Med := (Pri + Ult) Div 2;
      if Vec[Med].TimeOffset = Valor then Esta := true;
      if Vec[Med].TimeOffset < Valor then Pri:= Med + 1;
      if Vec[Med].TimeOffset > Valor then Ult:= Med - 1;
   end;
   if Esta then
     Result:= Med
   else
     Result:= Ult;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Inx: LongWord;
begin
  MostrarArreglo;
  Inx:= BuscarDB(1397); // Valor a buscar
  ShowMessage(Format('Index: %d Valor: %d',[Inx,Vec[Inx].TimeOffset]));
end;
...

Saludos.

[jars]

Gracias ECFISA, cumple perfectamente con lo que necesito.
Un abrazo.

jorge

[ecfisa]

De nada Jorge, un placer haberte sido de ayuda.

[jars]

Perdon que insista, y si quisiera encontrar el proximo mayor?

[ecfisa]

Hola Jorge.

En la función BuscarDB, reemplazá estas líneas:

Código Delphi [-]
 if Esta then
     Result:= Med
   else
     Result:= Ult;

Por:

Código Delphi [-]
 if Esta then
     Result:= Med
   else
     Result:= Pri;

Saludos

[jars]

Nuevamente gracias ecfisa