Búsqueda binaria o dicotómica
martes, 13 de octubre de 2009
Búsqueda binaria o dicotómica
Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos:{1,2,3,4}-5-{6,7,8,9}Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}Se vuelve a dividir el array en dos:{1}-2-{3,4}Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}Se vuelve a dividir en dos:{}-3-{4}Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería:int desde,hasta,medio,elemento,posicion; // desde y
// hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;)
{
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos:{1,2,3,4}-5-{6,7,8,9}Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}Se vuelve a dividir el array en dos:{1}-2-{3,4}Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}Se vuelve a dividir en dos:{}-3-{4}Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería:int desde,hasta,medio,elemento,posicion; // desde y
// hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;)
{
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
Etiquetas:
ed
APUNTES DE COMPUTACIÓN PARA ARQUITECTOS
lunes, 7 de septiembre de 2009
Que tal... jovenes de la carrera de Arquitectura...les dejo los apunde de la materia de computación que analizaremos en el transcurso de estos días. favor de descargarlo y elaborar un resumen del tema de historia de las computadoras.
CLIC AQUI PARA IR A LA DESCARGA
sin mas por el momento les envio un cordial saludo
Etiquetas:
Apuntes
ANTOLOGÍA DE ANÁLISIS DE SISTEMAS DE INFORMACIÓN
Les dejo los apuntes que se utilizará en la materia de Análisis de Sistemas de Información, les pido de favor que la impriman y que analicen los archivos de ejemplos que lo acompañan; así como, la presentación que lleva anexa (DESARROLLAR RESUMEN, VALOR 100 PUNTOS).
Clic para ir a la descarga
Sin mas por el momento, les envío un cordial saludo.
Hasta muy pronto.
Etiquetas:
Apuntes
Apuntes de Redes de Computadoras
jueves, 27 de agosto de 2009
Hola que tal (alumnos de ISC)...
Les dejo los apuntes para la materia de Redes de Computadoras. Favor de descargarlo, para su posterior análisis en clase.
Clic aquí para ir a la descarga
atte. Armando Hernández Santis
Clic aquí para ir a la descarga
atte. Armando Hernández Santis
Etiquetas:
Apuntes
Suscribirse a:
Entradas (Atom)