Busqueda binaria en archivos

[al_fc]

Saludos a todos, alguien sabe como hago una busqueda binaria en un archivo, se los agradecere si me ayudan

[latindeveloper]

Que estructura tiene el archivo?

[al_fc]

Que estructura tiene el archivo?

Para empezar lo que tengo que hacer es un directorio de contactos se manejan archivos 4 archivos secuenciales.

*El primero es el archivo de datos que contiene los campos:
codigo, primer nombre, segundo nombre, primer apellido, segundo apellido, fecha de nacimiento, telefono y direccion.

*El segundo archivo es el indice de codigo que es uno de los que tengo que hacer la busqueda, contiene los campos:
codigo y el rrn del archivo de datos.

*El tercer archivo es el de nombre que tiene los campos nombre y el next de una lista invertida que es el cuarto archivo donde esta el rrn y el anterior cuando hay nombres repetidos.

Lo unico que quiero saber es la busqueda con un ejemplo bastará.

[latindeveloper]

Voy a darte una idea (por que aun tengo dudas sobre tus archivos):

Dupongamos que LEN es el tamaño del registro (todos los campos). Si es constante entonces la cosa es mas facil, pero si es variable entonces se complica un poco pero al final es casi lo mismo pero los archivos ocupan menos espacio.

Cada registro en tu archivo de datos ocupa LEN bytes, si tienes por ejemplo 10 mil registros y quieres ubicar el registro nro 560 (empezando desde cero) entonces tendrías que moverte 560*LEN leer el archivo y volcarlo en una estructura. Supongamos que 560*LEN es la posicion del registro que tiene el codigo "BGTDTY".

Entonces seguramente en algun archivo de indice existe un registro de esta manera:

Posicion_Fisica Codigo
----------------- --------
560*LEN BGTDTY

Estos campos tienen que estar NECESARIAMENTE ordenados para efectuar una busqueda binaria.

La busqueda binaria se efectua de igual manera que en un array, la unica diferencia es que cuando te mueves lo haces SOBRE EL ARCHIVO.

Para buscar el codigo "BGTDTY" tendría que hacer lo siguiente: (pseudocodigo inventado por mi)

Código: Seleccionar todo

int BuscarRecursivoBinario (nInicio, nFin, ArchivoIndice,  TextoBuscado  =/*BGTDTY*/)
{
   nMitad = (nFin-nInicio)/2;
   ArchivoIndice.MoverHasta(nMitad);
   LeerRegistro(strRegActual,ArchivoIndice);

   if (strRegActual >  TextoBuscado )
   {
        return BuscarRecursivoBinario(nMitad,nFin,ArchvoIndice,TextoBuscado);
   }
  else
  {
        return BuscarRecursivoBinario(nInicio,nMitad,ArchvoIndice,TextoBuscado);
  }
}

Nota. En el codigo no esta considerado la condicion de parada (cuando no encuentre nada o encuentre algo...)

BuscarRecursivoBinario debe retornar la posicion fisica donde se encuentra el dato que estas buscando.

Espero haberte explicado ...

Saludos

PD. no se como pude escribir tanto en tan pocos minutos...

[al_fc]

Voy a darte una idea (por que aun tengo dudas sobre tus archivos):

Dupongamos que LEN es el tamaño del registro (todos los campos). Si es constante entonces la cosa es mas facil, pero si es variable entonces se complica un poco pero al final es casi lo mismo pero los archivos ocupan menos espacio.

Cada registro en tu archivo de datos ocupa LEN bytes, si tienes por ejemplo 10 mil registros y quieres ubicar el registro nro 560 (empezando desde cero) entonces tendrías que moverte 560*LEN leer el archivo y volcarlo en una estructura. Supongamos que 560*LEN es la posicion del registro que tiene el codigo "BGTDTY".

Entonces seguramente en algun archivo de indice existe un registro de esta manera:

Posicion_Fisica Codigo
----------------- --------
560*LEN BGTDTY

Estos campos tienen que estar NECESARIAMENTE ordenados para efectuar una busqueda binaria.

La busqueda binaria se efectua de igual manera que en un array, la unica diferencia es que cuando te mueves lo haces SOBRE EL ARCHIVO.

Para buscar el codigo "BGTDTY" tendría que hacer lo siguiente: (pseudocodigo inventado por mi)

Código: Seleccionar todo

int BuscarRecursivoBinario (nInicio, nFin, ArchivoIndice,  TextoBuscado  =/*BGTDTY*/)
{
   nMitad = (nFin-nInicio)/2;
   ArchivoIndice.MoverHasta(nMitad);
   LeerRegistro(strRegActual,ArchivoIndice);

   if (strRegActual >  TextoBuscado )
   {
        return BuscarRecursivoBinario(nMitad,nFin,ArchvoIndice,TextoBuscado);
   }
  else
  {
        return BuscarRecursivoBinario(nInicio,nMitad,ArchvoIndice,TextoBuscado);
  }
}

Nota. En el codigo no esta considerado la condicion de parada (cuando no encuentre nada o encuentre algo...)

BuscarRecursivoBinario debe retornar la posicion fisica donde se encuentra el dato que estas buscando.

Espero haberte explicado ...

Saludos

PD. no se como pude escribir tanto en tan pocos minutos...

Gracias por la ayuda me ha despejado la duda ya tengo una idea como hacerlo.