Nuevo algoritmo de búsqueda en vector

En este post os voy a explicar un nuevo algoritmo para buscar un elemento en un vector (también llamado array) ordenado. Este algoritmo es de mi invención y, al ser un poco más inteligente que la busqueda dicotómica, mejora el tiempo de búsqueda en algunos casos.

Repaso de los algoritmos de busqueda conocidos

Algoritmo secuencial

Se trata de ir elemento a elemento del vector comparándolo con el elemento a buscar.

i=0;
pos=0;
encontrado=falso;
mientras(i<array.length && encontrado){
  if(array[i]==elemento){
     encontrado=true
   }
}

Si encontrado es true la posición donde está el elemento es i. Sino, no está.

Busqueda dicotómica

Vamos a la mitad  del trozo del vector en el que estamos haciendo la búsqueda-inicialmente el trozo es el vector entero. Si en la mitad está el elemento, dejamos de buscar porque ya lo hemos encontrado. Si el valor de la posición de la mitad es menor que el elemento buscado, buscamos en el trozo que va de la mitad+1 al final del trozo. Si es mayor buscamos en el trozo que va del inicio del trozo hasta la posición mitad -1

buscar_dicotomica(inicio_trozo,final_trozo,elemento,vector){
  mitad=inicio_trozo + (final_trozo-inicio_trozo)/2
  if(vector[mitad]==elemento){
    encontrado=true
  }
  else if(inicio_trozo>final_trozo){
    encontrado=false
  }
  else if(vector[mitad]>elemento){
    buscar_dicotomica(inicio_trozo,mitad,elemento,vector)
 }
 else if(vector[mitad]<elemento){
   buscar_dicotomica(mitad,final_trozo,elemento,vector)
 }

}
buscar_dicotomica(0,N,elemento,vector)

Nuevo algoritmo

Este algoritmo es una variación de la busqueda dicotómica pero en vez de ir siempre a la mitad del trozo buscado, vamos a la posición proporcional respecto al tamaño del trozo a buscar –al inicio todo el vector– y la diferencia entre el valor que hay en el inicio del trozo y el valor que hay en el final del trozo.

Es decir,

Sea:

• N: posición final del trozo del vector donde estamos buscando
• k: posición inicial del trozo del vector donde estamos buscando
• v: vector en el que estamos buscando
• Propi: posición donde se encuentra el elemento
• e:elemento a buscar

Nuestra hipotesis es:

(N-K) → v[N]-v[K]

Propi-k → e –a[K]

Es decir, que la distancia de la posición K a la posición propi es proporcional al valor e –hipotéticamente el valor de a[propi]– menos el valor de a[k]:

(N-K)/(propi-k) = (v[N]-v[K])/e-a[k]

Una vez despejada propi:

Propi = ((N-k)*(e-v[k]))/(v[N]-v[k])+k

Si v[Propi] no es el elemento buscado se procede de forma similar a la búsqueda dicotómica. Si v[propi] es mayor que el elemento buscado se busca el elemento en el trozo de vector que va desde la posición propi+1 a N. Si, por el contrario, es menor, se busca el elemento en el trozo de vector que va desde la posición K a la posición propi-1.

De esta manera, el nuevo algoritmo expuesto es una mejora de la búsqueda dicotómica, ya que es un poco más inteligente a la hora de escoger el elemento del vector donde puede estar el valor.

encontrar_inversión (v, K, N, e){ 
  if(K>N){
    encontrado=false
  }
  else{
   Propi= ((N-K)(e-v[K])/v[N]-v[k])+K  
   if( a[propi]= e){
    encontrado=true;
   }
   else if( a[propi]<e){
    encontrar_inversion(v,K,propi,e);
   }
   else{
    encontrar_inversion(v,propi,N,e);
   }
 }
}

En próximos artículos presentaremos los resultados hechos de comparar el algoritmo dicotómico con el nuevo algoritmo.