busqueda indexada sin array intermedio
Luzem was here - 11-05-2005 03:01:50 | Categoria: Programación
metodos de BusquedaResulta que en clase nos estan enseñando metodos de busqueda asi que con el metodo de busqueda indexada defendi que el metodo podia funcionar sin array intermedio, creo que con esto puede valer, abajo teneis el acceso al codigo fuente
/*
* Algoritmo.java
*
* Created on 6 de mayo de 2005, 14:48
*/
package busquedaindexada;
/**
* La clase Algoritmo intenta muestra como realizar una busqueda
* indexada sin la utilización de un array auxiliar para guardar
* los indices
* @author Ninfa
* @mail luzemail@gmail.com
* @web http://www.luzem.bitacoras.com
* @since JDK 1.5.01
* @version 0.5 unestable && Beta
*/
public class Algoritmo {
/*Atributos*/
/**
* Esta variable almacenara el array donde se realizara la busqueda
*/
int lista[]; //Vector donde se realizara la busqueda
/**
* almacena el numero de elementos que contendra cada bloque de elementos
*/
int lenBloque;//Longitud de cada bloque
/**
* Creates a new instance of Algoritmo
* @param vector array donde se realizara la busqueda
* @param escala establece el numero de elementos que habra
* entre los distintos bloques que generara el vector
*/
public Algoritmo(int vector[],int escala) {
lista=new int[vector.length];
/*Copiamos el vector de entrada en lista
supongo que asignandolo con un = simple tambien
seria valido ya que lista referenciaria a vector[]*/
for (int x=0;x<vector.length;x++) {
lista[x]=vector[x];
}
lenBloque=escala;
}
/*Metodos*/
/**
* Obtiene el numero de elementos que forman el array auxiliar que
* utilizaremos mediante sencillos calculos
* @return Devuelve la longitud del array auxiliar
*/
public int getLongitudArrayAuxiliar() {
return(lista.length/lenBloque);
}
/**
* Devuelve el contenido de una posicion del array imaginario
* @param posArrayVirtual el indice que se desea obtener del array imaginario
* @return el contenido de la posicion que correspendo con el array
* imaginario
*/
public int getContentAt(int posArrayVirtual) {
return(lista[posArrayVirtual*lenBloque]);
}
/**
* este metodo se utiliza para realizar una busqueda binaria en el array
* de forma indexada, dicha busqueda se realiza de forma recursiva
* @return la posicion donde el indice tiene el mismo contenido
* que valor o la ocurrencia mas cercana
* @param valor el valor numerico a buscar en el array
* @param maxValue Valor mas alto del array donde realizar la busqueda
* @param minValue aqui se mete el extremo inferior de la busqueda
*/
public int busqueda(int valor,int maxValue,int minValue) {
int medio=maxValue-((maxValue-minValue)/2); /*punto_medio=Maximo -mitad(distancia max-min);*/
System.out.println("LLamada medio="+medio +" maxValue= "+maxValue+" minValue= "+minValue );
/*Casos de salida*/
if (minValue>maxValue)//El elemento no esta;
{
System.out.println("valor minimo "+minValue+" superior a valor maximo "+maxValue);
return (maxValue);//Retornamos la posicion de inserccion para dejar el algoritmo mas reusable
}
if (getContentAt(medio)==valor)
{
System.out.println("Valor a buscar="+valor+ " encontrado en la posicion "+medio+" verifica contenido= "+this.getContentAt(medio));
return (medio);
}
if (getContentAt(medio)>valor)
{
//Caso en que el valor de arrayVirtualde[medio] sea mayor que el valor
System.out.println("llamada en caso mayor");
return(busqueda(valor,medio-1,minValue));
}
else
{
//Caso en que el valor de arrayVirtualde[medio] sea menor que el valor
System.out.println("llamada en caso menor");
return(busqueda(valor,maxValue,medio+1));
}
//System.out.println("Bug_Bug_Bug");
//return (medio);
//Cuando entra aqui significa que los valores no coinciden
/**************************
*Caso de que punto medio *
*sea MAYOR que el pivote *
**************************/
}
/**
* método para obtener una cadena de texto con los atributos de la
* clase
* @return Una cadena de texto con los atributos de la clase
*/
public String toString() {
return("Array a ordenar "+lista+" longitud de bloqueo:"+lenBloque);
}
/**
* Metodo de "arrancada"
* @param args Parametros en caso de que se invoque a la aplicacion desde
* una consola, en este caso son INUTILES ya que son ignorados
*/
public static void main(String []args) {
int arraytemp[]=new int[1000];
for (int x=0;x<arraytemp.length;x++)
{
arraytemp[x]=x;
}
Algoritmo lanzado=new Algoritmo(arraytemp,10);
lanzado.busqueda(30,lanzado.getLongitudArrayAuxiliar()-1,0);
}
}
Si quereis bajar todo el codigo con una interfaz grafica que esta sin acabar aqui teneis el link Codigo busqueda indexada
Si quereis mas apuntes sobre algoritmos de busqueda los teneis en la pagina de mis profesores aqui
Comentarios (0) - Referencias (0)
