Interpolation Search [ Codigo En C++ ]

Cuando Queremos hacer una busqueda en un arreglo lo mas rapido que se nos viene a la mente es hacer un busqueda secuencial que consisite en comparar cada elemento y si es el numero que termine la busqeuda y si no lo es que siga recorriendo, otros pensaran en hacer una busqueda binaria basada en "Divide Y Venceras", Otros pensaran en el Interpolation Search o tambiern llamado Interpolacion de Busqueda, y en que consiste ezactamente este algoritmo, bueno es un algoritmo que tiene un parecido ala busqueda mediante claves o hashing en archivos.

FUNCION

bool I_Search(int *A, int N, int num )
{
int primero = 0;
int ultimo = N-1;
int medio;
int cont=0;

while( A[primero] != num && cont<=N )
      {
       medio = primero + ((num - A[primero])*
              (ultimo-primero))/(A[ultimo]-A[primero]);


      if(A[medio]
          primero = medio +1;

      else if(A[medio]>num)
          ultimo = medio-1;

      else
          primero = medio;

       cont++;

      }

if(A[primero]==num)
    return true;

else
   return false;
}

Por Ejemplo , Tenemos el siguiente arreglo:

Los Ordenamos Mediante cualquier metodo de ordenacion:

Si Queremos Buscar el numero 2 :

RECORRIDO #1:

medio = primero + ((num - A[primero])*(ultimo-primero))/(A[ultimo]-A[primero]);
4 = 0 +((2--8)*(5-0)/(4--8))

Como A[medio] que tiene como valor 3 es mayor que el numero a buscar 2
else if(A[medio]>num)
ultimo = medio-1;

3 = 4 - 1

RECORRIDO #2:

medio = primero + ((num - A[primero])*(ultimo-primero))/(A[ultimo]-A[primero]);
3 = 0 +((2--8)*(3-0)/(2--8))

Como A[medio] que tiene como valor 2 no es mayor ni menor que el numero a buscar 2
else
primero = medio;
3 = 3 ;

A[primero] que tiene como valor 2 while( A[primero] != num ) no cumple la condicion
EL NUMERO HA SIDO ENCONTRADO!!!!

#include<cstdio>
#include<cstdlib>
#define MAX 10000


int *ingresar(int *A, int N)
{
 A = new int [MAX];
 
 int i = 0 , j = 0;
 
 for (i = N - 1; i >= 0; --i)  
     {
      printf("\n\t\t\t\t - A [%d] : ",j);
      scanf("%d",&A[j]);
      j++;
     }
 return A;              
}

int *Ordenar (int *A, int n)
{
 int B;

 for ( int i = n - 1 ; i >= 1 ; i-- )
     for( int j = 0 ; j <= i - 1 ; j++ )
         if ( A[j] > A[j+1])
             {
              B = A[j];
              A[j] = A[j+1];
              A[j+1] = B;
             }
  
  return A;
}

bool I_Search(int *A, int N, int num )
{
 int primero = 0;
 int ultimo = N-1;
 int medio;
 int cont=0;  
  
 while( A[primero] != num && cont<=N )
      {
       medio = primero + ((num - A[primero])*
              (ultimo-primero))/(A[ultimo]-A[primero]);
    

      if(A[medio]<num)
          primero = medio +1;
         
      else if(A[medio]>num) 
          ultimo = medio-1;

      else 
          primero = medio;

       cont++;
 
      }
      
 if(A[primero]==num)
    return true;
 
 else 
   return false;      
}



int main()
{


 int *A = NULL;
 int N , Num ;
 bool valor = false;
 
 printf("\n\n\t Ingresar Longitud del Arreglo : ");
 scanf("%d",&N);
 
 A = ingresar( A , N );
 
 A = Ordenar ( A , N );

 
 
 printf("\n\n\t Ingresar Numero A Buscar : ");
 scanf("%d",&Num);
 
 valor = I_Search( A , N , Num );
 
  
 if (valor == true )
     printf("\n\n\t\t\t\t El %d esta en el " 
                "Arreglo ...\n\n",Num);
 
 else
     printf("\n\n\t\t\t\t El %d No esta en "
             "el Arreglo ...\n\n",Num);

system("pause");
 return 0;
}

Código Informático

Interpolation Search [ Codigo En C++ ]

1 comentarios: