Unidad 2. Arreglos.ppt

ORDENACIÓN Y ORDENACIÓN Y BÚSQUEDA EN BÚSQUEDA EN ARREGLOS.ARREGLOS.

Ordenación y Búsqueda en Ordenación y Búsqueda en ArreglosArreglos

Ordenamiento y búsqueda son las Ordenamiento y búsqueda son las operaciones básicas en el campo de operaciones básicas en el campo de la informática y en los que, según la informática y en los que, según señalan las estadísticas, las señalan las estadísticas, las computadoras emplean la mitad de computadoras emplean la mitad de su tiempo.su tiempo.

ConceptosConceptos

La La OrdenaciónOrdenación (clasificación) es la (clasificación) es la operación de organizar un conjunto operación de organizar un conjunto de datos en algún orden dado, tal de datos en algún orden dado, tal como creciente o decreciente en como creciente o decreciente en datos numéricos, o bien en orden datos numéricos, o bien en orden alfabético.alfabético.

Operaciones típicas de ordenación Operaciones típicas de ordenación son: lista de números, archivo de son: lista de números, archivo de clientes de banco, nombres de una clientes de banco, nombres de una agenda telefónica, etc.agenda telefónica, etc.

ConceptosConceptos

La La búsquedabúsqueda de información, es al de información, es al igual que la ordenación, otra igual que la ordenación, otra operación muy frecuente en el operación muy frecuente en el tratamiento de información. La tratamiento de información. La búsqueda es una actividad que se búsqueda es una actividad que se realiza diariamente en cualquier realiza diariamente en cualquier aspecto de la vida.aspecto de la vida.

Algoritmos de OrdenaciónAlgoritmos de Ordenación

Algoritmo de IntercambioAlgoritmo de IntercambioAlgoritmo de SelecciónAlgoritmo de SelecciónAlgoritmo de Inserción directaAlgoritmo de Inserción directaAlgoritmo QuickSortAlgoritmo QuickSort

Algoritmo de IntercambioAlgoritmo de Intercambio

El algoritmo de intercambio se basa El algoritmo de intercambio se basa en la idea de buscar cada vez el en la idea de buscar cada vez el menor elemento del conjunto y menor elemento del conjunto y ubicarlo al principio del mismo, ubicarlo al principio del mismo, repitiendo este proceso cada vez con repitiendo este proceso cada vez con el conjunto sin su primer elemento el conjunto sin su primer elemento (el menor del conjunto anterior), (el menor del conjunto anterior), hasta llegar a un conjunto de un solo hasta llegar a un conjunto de un solo elemento que por definición ya está elemento que por definición ya está ordenado.ordenado.

EjemploEjemplo

Ordenar los siguientes elementos:Ordenar los siguientes elementos:

Se toma el primer elemento (18) y se Se toma el primer elemento (18) y se compara con cada uno de los compara con cada uno de los elementos a su derecha, si el elementos a su derecha, si el elemento a su derecha es menor, se elemento a su derecha es menor, se intercambia y se continua intercambia y se continua comparando con los elementos comparando con los elementos restantes.restantes.

1818 2525 1212 66

¿ 18 > 25?¿ 18 > 25?

¿ 18 > 12 ?¿ 18 > 12 ?

EjemploEjemplo

1818 2525 1212 66

1818 2525 1212 66

¿ 12 > 6 ?¿ 12 > 6 ?

EjemploEjemplo

1212 2525 1818 66

66 2525 1818 1212

Como ya no quedan elementos a la Como ya no quedan elementos a la derecha, termina esta iteración. Hasta derecha, termina esta iteración. Hasta este momento, se ha colocado el este momento, se ha colocado el elemento menor en la primera posición, elemento menor en la primera posición, ahora se toma el siguiente elemento (25), ahora se toma el siguiente elemento (25), y se compara con sus elementos a la y se compara con sus elementos a la derecha.derecha.

¿ 25 > 18 ?¿ 25 > 18 ?

EjemploEjemplo

66 2525 1818 1212

¿ 18 > 12 ?¿ 18 > 12 ?

EjemploEjemplo

66 1818 2525 1212

66 1212 2525 1818

Como ya no quedan elementos a la Como ya no quedan elementos a la derecha, termina esta iteración. Hasta derecha, termina esta iteración. Hasta este momento, se ha colocado el segundo este momento, se ha colocado el segundo elemento menor en la segunda posición, elemento menor en la segunda posición, ahora se toma el siguiente elemento (25), ahora se toma el siguiente elemento (25), y se compara con sus elementos a la y se compara con sus elementos a la derecha.derecha.

¿ 25 > 18 ?¿ 25 > 18 ?

EjemploEjemplo

66 1212 2525 1818

Como ya no quedan elementos a la Como ya no quedan elementos a la derecha, termina esta iteración. Hasta derecha, termina esta iteración. Hasta este momento, se ha colocado el tercer este momento, se ha colocado el tercer elemento menor en la tercera posición, elemento menor en la tercera posición, ahora se toma el siguiente elemento (25), ahora se toma el siguiente elemento (25), y se compara con sus elementos a la y se compara con sus elementos a la derecha.derecha.

EjemploEjemplo

66 1212 1818 2525

Como se trata del ultimo elemento, Como se trata del ultimo elemento, ya no existen mas elementos a la ya no existen mas elementos a la derecha. Por lo tanto, el proceso ha derecha. Por lo tanto, el proceso ha terminado y los elementos quedan terminado y los elementos quedan ordenados.ordenados.

EjemploEjemplo

66 1212 1818 2525

Código ….Código ….

public void ordenarIntercambio(int[] A){ int aux; for(int i = 0; i < A.length - 1; i++){ for(int j = i+1; j < A.length; j++){ if(A[j] < A[i]){ aux = A[i]; A[i] = A[j]; A[j] = aux; } } } }

Public void intercambio(int[] M){int aux;int t = M.length;for (inti = 1; i< t; i++) {for (int j = t- 1; j >= i; j--) {if(M[j] < M[j-1]) {aux = M[j];M[j] = M[j-1];M[j-1]= aux; } } }

Algoritmo de SelecciónAlgoritmo de Selección

La idea básica de este algoritmo La idea básica de este algoritmo consiste en buscar el menor consiste en buscar el menor elemento del arreglo y colocarlo en elemento del arreglo y colocarlo en la primera posición. Luego se busca la primera posición. Luego se busca el segundo elemento mas pequeño el segundo elemento mas pequeño del arreglo y se coloca en la segunda del arreglo y se coloca en la segunda posición. Después, se busca el tercer posición. Después, se busca el tercer elemento mas pequeño y se coloca elemento mas pequeño y se coloca en la tercera posición, y así en la tercera posición, y así sucesivamente hasta que el arreglo sucesivamente hasta que el arreglo quede ordenado.quede ordenado.

EjemploEjemplo


Primero, se busca el elemento menor Primero, se busca el elemento menor (6) dentro del arreglo y se coloca en (6) dentro del arreglo y se coloca en la primera posición.la primera posición.

1818 2525 1212 66

EjemploEjemplo

El número 6 es el elemento menor, El número 6 es el elemento menor, por lo tanto se coloca en la primera por lo tanto se coloca en la primera posición intercambiándolo por el posición intercambiándolo por el elemento que se encuentra elemento que se encuentra actualmente en esa posición.actualmente en esa posición.

1818 2525 1212 66

A continuación, se busca el segundo A continuación, se busca el segundo elemento menor (12) del arreglo y se elemento menor (12) del arreglo y se coloca en la segunda posición coloca en la segunda posición intercambiándolo por el elemento intercambiándolo por el elemento que se encuentre actualmente en que se encuentre actualmente en esa posición.esa posición.

66 2525 1212 1818

Después, se busca el tercer Después, se busca el tercer elemento menor (18) del arreglo y se elemento menor (18) del arreglo y se coloca en la tercera posición. coloca en la tercera posición.

66 1212 2525 1818

Por ultimo, se busca el cuarto Por ultimo, se busca el cuarto elemento menor (25) del arreglo y se elemento menor (25) del arreglo y se coloca en la cuarta posición. coloca en la cuarta posición.

Debido a que ya no existen mas Debido a que ya no existen mas elementos, el arreglo queda elementos, el arreglo queda ordenado.ordenado.

66 1212 1818 2525


public void ordenarSeleccion(int[] A){ int aux; int menor; for(int i = 0; i < A.length - 1; i++){ menor = i; for(int j = i+1; j < A.length; j++){ if(A[j] < A[menor]){ menor = j; } } if(menor != i){ aux = A[i]; A[i] = A[menor]; A[menor] = aux; } } }

public void seleccion(int[] M) {Int menor;int aux; for(inti=0; i<M.length-1; i++) {menor=i;for(int d=i+1; i<M.length; d++) {if(M[d]<M[menor]) {menor=d; } }aux=M[i]; M[i]=M[menor]; M[menor]=aux; } }

Algoritmo de Inserción Algoritmo de Inserción DirectaDirecta

El algoritmo consiste en realizar varias pasadas sobre el arreglo. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente.

Cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del arreglo han sido analizados, la lista está completamente ordenada. En cada pasada no se recorre todo el arreglo, sino solo los elementos analizados y ordenados en pasadas anteriores.

EjemploEjemplo


Primero, se empieza desde el Primero, se empieza desde el segundo elemento del arreglo (52) y segundo elemento del arreglo (52) y se compara con el anterior (45), se compara con el anterior (45), como 52 es mayor a 45 se detiene como 52 es mayor a 45 se detiene la iteración y se continúa con el la iteración y se continúa con el siguiente elemento.siguiente elemento.

4545 5252 2121 3737 1414

EjemploEjemplo


Después, se toma el siguiente valor Después, se toma el siguiente valor (21) y se compara con el elemento (21) y se compara con el elemento anterior (52), como 21 es menor a anterior (52), como 21 es menor a 52 entonces se intercambian los 52 entonces se intercambian los valores.valores.

4545 5252 2121 3737 1414

EjemploEjemplo


Después, se compara el 21 con el Después, se compara el 21 con el siguiente valor (45), como 21 es siguiente valor (45), como 21 es menor a 45 entonces se menor a 45 entonces se intercambian.intercambian.

4545 2121 5252 3737 1414

EjemploEjemplo


En este momento, el 21 está en el En este momento, el 21 está en el lugar que le corresponde, por lo lugar que le corresponde, por lo tanto termina la iteración.tanto termina la iteración.

2121 4545 5252 3737 1414

EjemploEjemplo


Ahora, se toma el siguiente valor Ahora, se toma el siguiente valor (37) y se va recorriendo con los (37) y se va recorriendo con los elementos anteriores hasta elementos anteriores hasta encontrar la posición que le encontrar la posición que le corresponde.corresponde.

2121 4545 5252 3737 1414

EjemploEjemplo


Se compara el (37) con el (52), como Se compara el (37) con el (52), como 37 es menor a 52 entonces se 37 es menor a 52 entonces se intercambian los valores y se intercambian los valores y se continúa con el siguiente.continúa con el siguiente.

2121 4545 5252 3737 1414

EjemploEjemplo


Ahora se compara el (37) con el (45), Ahora se compara el (37) con el (45), como 37 es menor a 45 entonces se como 37 es menor a 45 entonces se intercambian los valores y se intercambian los valores y se continúa con el siguiente.continúa con el siguiente.

2121 4545 3737 5252 1414

EjemploEjemplo


Ahora se compara el (37) con el (21), Ahora se compara el (37) con el (21), como 37 no es menor a 21 entonces como 37 no es menor a 21 entonces se termina la iteración y se continúa se termina la iteración y se continúa con el siguiente valor.con el siguiente valor.

2121 3737 4545 5252 1414

EjemploEjemplo


Ahora, se toma el siguiente valor Ahora, se toma el siguiente valor (14) y se va recorriendo con los (14) y se va recorriendo con los elementos anteriores hasta elementos anteriores hasta encontrar la posición que le encontrar la posición que le corresponde.corresponde.

2121 3737 4545 5252 1414

EjemploEjemplo


Se compara el (14) con el (52), como Se compara el (14) con el (52), como 14 es menor a 52 entonces se 14 es menor a 52 entonces se intercambian los valores y se intercambian los valores y se continúa con el siguiente.continúa con el siguiente.

2121 3737 4545 5252 1414

EjemploEjemplo



2121 3737 4545 1414 5252

EjemploEjemplo



2121 3737 1414 4545 5252

EjemploEjemplo


Ahora se compara el (14) con el (21), Ahora se compara el (14) con el (21), como 14 es menor a 21 entonces se como 14 es menor a 21 entonces se intercambian los valores, como ya no intercambian los valores, como ya no existen mas elementos por analizar existen mas elementos por analizar se termina la iteración.se termina la iteración.

2121 1414 3737 4545 5252

EjemploEjemplo


Como ya no existen mas elementos Como ya no existen mas elementos por analizar, se termina el algoritmo por analizar, se termina el algoritmo y como resultado se tiene el arreglo y como resultado se tiene el arreglo ordenado.ordenado.

1414 2121 3737 4545 5252


public void AlgoritmoInsercion(int[] A){ //empezamos por el segundo (1) y terminamos //en el último (n-1) for (int i = 1; i < A.length; i++) { //guardamos el valor del elemento i int temp = A[i]; //empezamos a compararlo con el anterior int j = i - 1; //y seguimos mientras no hayamos llegado //al principio del arreglo y los elementos //que encontremos sean mayores que el que //analizamos while (j >= 0 && A[j] > temp) { //desplazamos el elemento un //lugar a la derecha A[j + 1] = A[j]; //y pasamos al anterior j--; } //Al terminar el ciclo, j indica el //lugar inmediatamente anterior a donde //debemos encajar v A[j + 1] = temp; }}

public void insercion(int[] M) {int temp;int j;for(inti=1; i<M.length; i++) {temp=M[i]; j= i - 1;while(j>=0 && M[j]<temp) {M[j+1]=temp; } }

Algoritmo QuickSortAlgoritmo QuickSort

El método de ordenación QuickSort El método de ordenación QuickSort es actualmente el más eficiente y es actualmente el más eficiente y veloz de los métodos de ordenación. veloz de los métodos de ordenación.

Este algoritmo se basa Este algoritmo se basa principalmente en la técnica de principalmente en la técnica de divide y vencerás.divide y vencerás.

DefiniciónDefinición

La idea central de este algoritmo consiste en lo La idea central de este algoritmo consiste en lo siguiente:siguiente: Se toma un elemento X de una posición Se toma un elemento X de una posición

cualquiera del arreglo.cualquiera del arreglo. Se trata de ubicar a X en la posición correcta Se trata de ubicar a X en la posición correcta

del arreglo, de tal forma que todos los del arreglo, de tal forma que todos los elementos que se encuentren a su izquierda elementos que se encuentren a su izquierda sean menores o iguales a X y todos los sean menores o iguales a X y todos los elementos que se encuentren a su derecha elementos que se encuentren a su derecha sean mayores a X.sean mayores a X.

Se repiten los pasos anteriores pero ahora Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición a la izquierda y a la derecha de la posición correcta de X en el arreglo.correcta de X en el arreglo.

El proceso termina cuando todos los El proceso termina cuando todos los elementos se encuentran en su posición elementos se encuentran en su posición correcta del arreglo.correcta del arreglo.

EjemploEjemplo

Declaramos el primer elemento del Declaramos el primer elemento del arreglo como arreglo como primeroprimero y al ultimo como y al ultimo como ultimo.ultimo.

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

primero ultimo

EjemploEjemplo

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

pivote

primero ultimo

Declaramos el primer elemento como el Declaramos el primer elemento como el pivote del arreglo.pivote del arreglo.

Colocamos UP como primero y Colocamos UP como primero y DOWN como ultimo.DOWN como ultimo.

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

pivote

primero ultimo

UP DOWN

Mover UP al primer valor mayor al pivote.Mover UP al primer valor mayor al pivote.

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

primero ultimo

UP DOWN

Mover DOWN al primer valor de derecha a Mover DOWN al primer valor de derecha a izquierda menor al pivote (en este caso DOWN no izquierda menor al pivote (en este caso DOWN no se mueve.se mueve.

pivote

Se intercambian los valores de UP y Se intercambian los valores de UP y DOWNDOWN

4444 7575 2323 4343 5555 1212 6464 7777 3333

0 1 2 3 4 5 6 7 8

primero ultimo

UP DOWN

4444 3333 2323 4343 5555 1212 6464 7777 7575

0 1 2 3 4 5 6 7 8

pivote

Desde la posición en que se encuentra, movemos Desde la posición en que se encuentra, movemos UP a un valor mayor al pivote.UP a un valor mayor al pivote.

4444 3333 2323 4343 5555 1212 6464 7777 7575

primero ultimo

UP DOWN

4444 3333 2323 4343 5555 1212 6464 7777 7575

primero ultimo

UP DOWN

pivote

pivote

Cambiamos DOWN a la posición menor Cambiamos DOWN a la posición menor que el pivote recorriendo de derecha a que el pivote recorriendo de derecha a izquierda izquierda

4444 3333 2323 4343 5555 1212 6464 7777 7575

primero ultimo

UP DOWN

pivote

Intercambiamos los valores de UP y Intercambiamos los valores de UP y DOWN.DOWN.

4444 3333 2323 4343 5555 1212 6464 7777 7575

primero ultimo

UP DOWN

4444 3333 2323 4343 1212 5555 6464 7777 7575

pivote

4444 3333 2323 4343 1212 5555 6464 7777 7575

primero ultimo

UP DOWN

Movemos UP desde la posición en que se encuentra, a Movemos UP desde la posición en que se encuentra, a la primera posición mayor que el pivote y DOWN a la la primera posición mayor que el pivote y DOWN a la primera posición de derecha a izquierda menor que primera posición de derecha a izquierda menor que el pivote.el pivote.

4444 3333 2323 4343 1212 5555 6464 7777 7575

primero ultimo

UP DOWN

pivote

pivote

Como UP y DOWN se cruzaron, entonces Como UP y DOWN se cruzaron, entonces debemos intercambiar el valor de DOWN por el debemos intercambiar el valor de DOWN por el pivote.pivote.

1212 3333 2323 4343 4444 5555 6464 7777 7575

primero ultimo

UP

DOWNpivote

Ahora notemos que todos los valores a la izquierda de Ahora notemos que todos los valores a la izquierda de pivote son menores que el, y los que estan a la derecha pivote son menores que el, y los que estan a la derecha son mayores que elson mayores que el.

pivote

Ahora se tienen dos sub arreglos. Un arreglo con los elementos menores al pivote y otro arreglo con los elementos mayores al pivote.

1212 3333 2323 4343 4444 5555 6464 7777 7575

pivote

1212 3333 2323 4343 4444 5555 6464 7777 7575

primero 1 primero 2ultimo 1 ultimo 2

Se debe repetir el mismo proceso hasta que los nuevos sub arreglos queden ordenados, esto dará como resultado el arreglo original ordenado.


public int moverPivote(int[] A, int primero, int ultimo) { int pivote = A[primero], UP = primero, DOWN = ultimo, aux;

while (UP < DOWN) { while (UP <= ultimo && A[UP] <= pivote) UP++; while (DOWN >= primero && A[DOWN] > pivote) DOWN--;

if (UP < DOWN) { aux = A[UP]; A[UP] = A[DOWN]; A[DOWN] = aux; UP++; DOWN--; }

}

if (DOWN >= 0 && A[DOWN] != pivote) { A[primero] = A[DOWN]; A[DOWN] = pivote; }

return DOWN;

}

QuickSortFloatArray(float[] ArrayNumeros, int Inicio, int Fin) { int InicioLocal= Inicio, FinLocal=Fin; float Temp, Pivote; if(Fin>Inicio) { Pivote= ArrayNumeros[(Inicio+Fin)/2]; while(InicioLocal<FinLocal) { while((InicioLocal<Fin) && (ArrayNumeros[InicioLocal]<Pivote)) ++InicioLocal; while((FinLocal>Inicio) && (ArrayNumeros[FinLocal]>Pivote)) --FinLocal; if(InicioLocal<=FinLocal) { Temp=ArrayNumeros[InicioLocal]; ArrayNumeros[InicioLocal]=ArrayNumeros[FinLocal]; ArrayNumeros[FinLocal]=Temp; ++InicioLocal; --FinLocal; } } if(Inicio<FinLocal) QuickSortFloatArray(ArrayNumeros,Inicio,FinLocal); if(InicioLocal<Fin) QuickSortFloatArray(ArrayNumeros,InicioLocal,Fin); } }

public void quicksort(int[] A, int primero, int ultimo){

if (primero >= ultimo || primero < 0) return;int indicePivote= moverPivote(A, primero, ultimo);quicksort(A, primero, indicePivote-1);quicksort(A, indicePivote + 1, ultimo);

}

public void quicksort(int x[],int primero,int ultimo) { int temp, UP=primero, DOWN=ultimo, pivote; if(ultimo>primero) { pivote=x[primero]; while(UP<=DOWN) { while((UP<ultimo)&&(x[UP]<pivote)) ++UP; while((DOWN>primero)&&(x[DOWN]>pivote)) --DOWN; if(UP<=DOWN) { temp = x[UP]; x[UP] = x[DOWN]; x[DOWN] = temp; ++UP; --DOWN; } } if(primero<DOWN) quicksort(x,primero,DOWN); if(UP<ultimo) quicksort(x,UP,ultimo); } }

RecursividadRecursividad

Permite definir un objeto (problema, Permite definir un objeto (problema, estructura de datos) en términos de estructura de datos) en términos de sí mismo.sí mismo.

Un Un algoritmo recursivoalgoritmo recursivo es un es un algoritmo que expresa la solución de algoritmo que expresa la solución de un problema en términos de una un problema en términos de una llamada a sí mismo. La llamada a sí llamada a sí mismo. La llamada a sí mismo se conoce como llamada mismo se conoce como llamada recursiva o recurrente.recursiva o recurrente.

RecursividadRecursividad

Directa: el subprograma se llama Directa: el subprograma se llama directamente así mismo.directamente así mismo.

Indirecta: el subprograma llama a Indirecta: el subprograma llama a otro subprograma, y éste a su vez otro subprograma, y éste a su vez llama al primero.llama al primero.

EjemploEjemplo

La función matemática La función matemática factorialfactorial se define se define como el producto de todos los números como el producto de todos los números hasta el argumento inclusive. El factorial hasta el argumento inclusive. El factorial de 1 es 1.de 1 es 1.

Por lo tanto:Por lo tanto:

1! = 1! = 112! = 1 x 2 = 2! = 1 x 2 = 223! = 1 x 2 x 3 = 2! x 3 = 3! = 1 x 2 x 3 = 2! x 3 = 664! = 1 x 2 x 3 x 4 = 3! x 4 = 4! = 1 x 2 x 3 x 4 = 3! x 4 = 24245! = 1 x 2 x 3 x 4 x 5 = 4! x 5 = 5! = 1 x 2 x 3 x 4 x 5 = 4! x 5 = 120120

6! = 1 x 2 x 3 x 4 x 5 x 6 = 5! x 6 6! = 1 x 2 x 3 x 4 x 5 x 6 = 5! x 6 = 720= 720


EjemploEjemplo

int factorial factorial(int n n) { if(nn<=1) { {

return 1; }}else{

return n n*factorialfactorial(nn-1); }}

}

EjemploEjemplo

En matemáticas, la En matemáticas, la sucesión de sucesión de FibonacciFibonacci es la es la siguiente sucesión infinita siguiente sucesión infinita de números naturales:de números naturales:

0, 10, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, , 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…144…

La sucesión inicia con La sucesión inicia con 0 y 10 y 1, y a partir , y a partir de ahí cada elemento es la suma de de ahí cada elemento es la suma de los dos anteriores.los dos anteriores.

Métodos de Búsqueda en Métodos de Búsqueda en ArreglosArreglos

Búsqueda SecuencialBúsqueda SecuencialBúsqueda BinariaBúsqueda Binaria

DefiniciónDefinición

La búsqueda en arreglos es un La búsqueda en arreglos es un proceso que consiste principalmente proceso que consiste principalmente en localizar o identificar la posición en localizar o identificar la posición de un elemento (numérico, cadena, de un elemento (numérico, cadena, booleano, etc) dentro de un conjunto booleano, etc) dentro de un conjunto de datos.de datos.

EjemplosEjemplos

Búsqueda de un número en un Búsqueda de un número en un directorio telefónico.directorio telefónico.

Búsqueda de un libro en una Búsqueda de un libro en una biblioteca o librería.biblioteca o librería.

Búsqueda de los datos de un Búsqueda de los datos de un empleado.empleado.

Etc…Etc…

Búsqueda SecuencialBúsqueda Secuencial

Consiste en revisar elemento por Consiste en revisar elemento por elemento hasta encontrar el dato o elemento hasta encontrar el dato o elemento deseado, o hasta llegar al elemento deseado, o hasta llegar al final de la lista de elementos final de la lista de elementos disponibles.disponibles.

Los dos posibles resultados de ésta Los dos posibles resultados de ésta búsqueda son:búsqueda son: La posición en que se encontró el La posición en que se encontró el

elemento.elemento. Un mensaje o valor representando que Un mensaje o valor representando que

no se encontró el elemento.no se encontró el elemento.

Búsqueda BinariaBúsqueda Binaria

Consiste en dividir el intervalo de Consiste en dividir el intervalo de búsqueda en dos partes, búsqueda en dos partes, comparando el elemento buscado comparando el elemento buscado con el central. En caso de no ser con el central. En caso de no ser iguales se redefinen los extremos del iguales se redefinen los extremos del intervalo (según el elemento central intervalo (según el elemento central sea mayor o menor que el buscado) sea mayor o menor que el buscado) disminuyendo el espacio de disminuyendo el espacio de búsqueda.búsqueda.

Búsqueda BinariaBúsqueda Binaria

Los dos posibles resultados de ésta Los dos posibles resultados de ésta búsqueda son:búsqueda son: La posición en que se encontró el La posición en que se encontró el

elemento.elemento. Un mensaje o valor representando que Un mensaje o valor representando que

no se encontró el elemento.no se encontró el elemento.

Este método funciona solamente Este método funciona solamente para arreglos ordenados. Con cada para arreglos ordenados. Con cada iteración del método el espacio de iteración del método el espacio de búsqueda se reduce a la mitad.búsqueda se reduce a la mitad.


int inicio = 0;nt inicio = 0; int fin = arreglo.length - 1; int fin = arreglo.length - 1; int pos; int pos; while (inicio <= fin) { while (inicio <= fin) { pos = (inicio+fin) / 2; pos = (inicio+fin) / 2; if ( arreglo[pos] == dato ) if ( arreglo[pos] == dato ) return pos; return pos; else if ( arreglo[pos] < dato ) { else if ( arreglo[pos] < dato ) { inicio = pos+1; } inicio = pos+1; } else { fin = pos-1; else { fin = pos-1; }} } } return -1; } return -1; } }} inicio = 0, fin = A.length-1, me return resultado; }

El siguiente método realiza la búsqueda binaria, regresa la posición en El siguiente método realiza la búsqueda binaria, regresa la posición en la que se encuentra el Valor a buscar, en caso de no encontrar el Valor la que se encuentra el Valor a buscar, en caso de no encontrar el Valor regresa un -1regresa un -1

Documents

Unidad 2. Arreglos.ppt