BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.6. BÚSQUEDA LINEAL Y BINARIA. (LINEAL AND BINARY SEARCH)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.6. BÚSQUEDA LINEAL Y BINARIA. (LINEAL AND BINARY SEARCH)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.6. BÚSQUEDA LINEAL Y BINARIA. (LINEAL AND BINARY SEARCH)

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Búsqueda Lineal y Binaria. (Lineal and Binary Search)

Para encontrar algo dentro de una estructura de datos los algoritmos más conocidos son la búsqueda lineal y binaria. Los dos métodos de búsqueda que se explican en este capítulo, se usarán con los mismos arreglos dinámicos antes vistos: LNaturales, LEnteros, LReales y LPalabras.

La búsqueda lineal también se conoce como búsqueda secuencial. El algoritmo de la búsqueda lineal es muy simple y consiste en ir comparando cada uno de los elementos de la lista, hasta encontrar el elemento buscado, a continuación un programa de ejemplo:


Descargar
{Codepage utf8}
Uses sysutils,Listas;

function BusquedaLineal(A:LNaturales; var pos:longword;k:qword):boolean;
Var i:longword;
  Begin
     i:=0;
     BusquedaLineal:=false;
     while (k<>A[i]) and (i<high(A)) do  i:=i+1;
     if A[i]=k then  BusquedaLineal:=true;
     pos:=i
  End;

Var A:LNaturales;      
     pos:longword; 
     k:qword;
Begin
   SetLength(A,3000000);
    ListaAleatoria(A,18446744073709551615);    
    Write('Ingrese un numero a buscar: '); Readln(k);
    
    Writeln(' Busqueda Lineal o Secuencial  ');
    if BusquedaLineal(A,pos,k)
       then Writeln('La primera ocurrencia existe en: ',pos,'  A[',pos,']=',A[pos])
       else Writeln('No existe');

End.
Código fuente 14: Algortimo Busqueda Líneal.
Descargar

La función BusquedaLineal devuelve verdadero cuando encuentra lo que se buscaba, y la posición lo devuelve en el parámetro pos, cuando no encuentra nada devuelve el valor falso y en pos se devuelve la posición del último elemento de la lista. Este algoritmo funcionará sin importar si la lista esta ordenada o desordenada.

La búsqueda binaria sólo se usa con listas ordenadas, tanto en orden ascendente como en orden descendente, este algoritmo es recomendado para listas de regular tamaño, la idea consiste en tomar el elemento central de la lista, si el elemento central es mayor que el que se está buscando, entonces el valor puede estar en la parte izquierda o superior de la lista, y se busca en esa parte tomando un nuevo elemento central y así sucesivamente, lo mismo se hace para la parte derecha o inferior hasta encontrar el número. Ejemplo:


Descargar
{Codepage utf8}
Uses sysutils,Listas;

Procedure Ordenar(var A:LNaturales;n:byte);
Procedure ContarPosicionar(A,B:LNaturales;i:longint);
Var j:longint;
      d:byte;
      pos:array [0..255] of longword;
 Begin
   FillDWord(pos,256,0);
   for j:=low(A) to high(A) do
        Begin
           d:=(A[j] shr ((8*i)-8)) and $FF;
           pos[d]:=pos[d]+1
        End;
   for j:=0 to 254 do pos[j+1]:=pos[j]+pos[j+1];
   for j:=high(A) downto low(A) do //ascendente
       Begin
          d:=(A[j] shr ((8*i)-8)) and $FF;
          pos[d]:=pos[d]-1;
          B[pos[d]]:=A[j]; //ascendente
       End;
 End;

 Var i:longint;
     B:LNaturales;
Begin
   SetLength(B,Length(A));
   for i:=1 to n do
      if (i mod 2)<>0
           then  ContarPosicionar(A,B,i)
           else   ContarPosicionar(B,A,i);
   if  (n mod 2)<>0  then  for i:=low(A) to  high(A) do A[i]:=B[i]
End;

function BusquedaBinaria(A:LNaturales; var pos:longword;k:qword):boolean;
Var primero,ultimo,mitad:longword;
    encontro:boolean;
Begin
  primero:=0;
  ultimo:=length(A)-1;
  encontro:=false;

  While (longint(ultimo)>=primero) and not(encontro) do
    Begin
       mitad:=(primero+ultimo) div 2;
       if A[mitad]=k then encontro:=true
       else
       if A[mitad]>k //ascendente
         then ultimo:=mitad-1
         else primero:=mitad+1;
    End;
  pos:=mitad;
  BusquedaBinaria:=encontro;
End;

Var A:LNaturales;
     pos:longword;
     k:qword;
     i:integer;
Begin
    SetLength(A,3000000);
    ListaAleatoria(A,18446744073709551615);
    Ordenar(A,8);
    Writeln('Busqueda Binaria  ');
    Write('Ingrese un numero a buscar: '); Readln(k);
    if BusquedaBinaria(A,pos,k)
       then Writeln('La primera ocurrencia existe en: ',pos,'  A[',pos,']=',A[pos])
       else Writeln('No existe ',pos);
End.
Código fuente 15: Algoritmo busqueda binaria ascendente.
Descargar

La función busquedabinaria usa las siguientes variables, primero, ultimo, mitad y una variable de tipo boolean encontro. Las variables ultimo y primero siempre tendrá los índices o posiciones de donde empiezan y terminan las partes en que se va dividiendo la búsqueda.

Al momento de ingresar al bucle while se toma la mitad del arreglo que será la suma del primero con el ultimo y dividido con 2, tomando sólo la parte entera. Una vez obtenido la posición media o la mitad se compara el elemento que se encuentra en esa posición, y si es igual entonces se sale del bucle haciendo que la variable encontro tome el valor true. En caso no sea igual se verifica si el elemento de la posición media o mitad es mayor que el valor buscado, que en este caso es el valor de la variable k. Si es mayor entonces a ultimo se le asigna la mitad menos 1, para seguir buscando en la parte superior o izquierda del arreglo, en caso contrario a primero se le asigna la mitad más 1, para segur buscando en la parte inferior o derecha del arreglo.

Debido a que primero y ultimo se irán acercando, conforme se realice la búsqueda o se vaya recorriendo el arreglo, el bucle while debe verificar si ultimo es mayor que primero, si ultimo es mayor que primero entonces se sigue con la busqueda, en caso contrario se termina el bucle. En caso se haya encontrado el valor buscado la variable mitad tendrá la posición en donde se encontró y la variable encontro tendrá el valor true.

Al comparar la variable ultimo con la variable primero, se hace un solapamiento de la variable ultimo con el tipo de dato longint, esto es debido a que si buscamos un valor menor que no se encuentre al inicio del arreglo, mitad tendría un cero que al restarle un 1 nos dará el valor más alto del tipo de dato longword, y el bucle continuaría. Al solapar el valor de ultimo con el tipo de dato longint, haremos que el valor más alto que tenga ultimo se convierta en un número negativo permitiendo de ese modo terminar el bucle.

En caso queramos hacer una búsqueda de un elemento en un lista ordenada en orden descendente, entonces se tiene que hacer un cambio en el algoritmo, este cambio sólo se hace al comparar el elemento medio con el elemento a buscar. En ves de usar el operador > se debe usar el operador <.


Descargar
{Codepage utf8}
Uses sysutils,Listas;

Procedure Ordenar(var A:LNaturales;n:byte);
Procedure ContarPosicionar(A,B:LNaturales;i:longint);
Var j:longint;
      d:byte;
      pos:array [0..255] of longword;
 Begin
   FillDWord(pos,256,0);
   for j:=low(A) to high(A) do
        Begin
           d:=(A[j] shr ((8*i)-8)) and $FF;
           pos[d]:=pos[d]+1
        End;
   for j:=0 to 254 do pos[j+1]:=pos[j]+pos[j+1];
   for j:=low(A) to high(A) do //descendente
       Begin
          d:=(A[j] shr ((8*i)-8)) and $FF;
          pos[d]:=pos[d]-1;
          B[high(B)-pos[d]]:=A[j]; //descendente
       End;
 End;

 Var i:longint;
     B:LNaturales;
Begin
   SetLength(B,Length(A));
   for i:=1 to n do
      if (i mod 2)<>0
           then  ContarPosicionar(A,B,i)
           else   ContarPosicionar(B,A,i);
   if  (n mod 2)<>0  then  for i:=low(A) to  high(A) do A[i]:=B[i]
End;

function BusquedaBinaria(A:LNaturales; var pos:longword;k:qword):boolean;
Var primero,ultimo,mitad:longword;
    encontro:boolean;
Begin
  primero:=0;
  ultimo:=length(A)-1;
  encontro:=false;
  While (longint(ultimo)>=primero) and not(encontro) do
    Begin
       mitad:=(primero+ultimo) div 2;
       if A[mitad]=k then encontro:=true
       else
       if A[mitad]<k //descendente
         then ultimo:=mitad-1
         else primero:=mitad+1;
    End;
  pos:=mitad;

  BusquedaBinaria:=encontro;
End;

Var A:LNaturales;
     pos:longword;
     k:qword;
     i:integer;
Begin
    SetLength(A,3000000);
    ListaAleatoria(A,18446744073709551615);
    Ordenar(A,8);
    Writeln('Busqueda Binaria  ');
    Write('Ingrese un numero a buscar: '); Readln(k);
    if BusquedaBinaria(A,pos,k)
       then Writeln('La primera ocurrencia existe en: ',pos,'  A[',pos,']=',A[pos])
       else Writeln('No existe ',pos);
End.
Código fuente 16: Algoritmo busqueda binaria descendente.
Descargar


Última revisión: 06/12/2014.



SIGUIENTE
SIGUIENTE
SIGUIENTE


 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.








PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.