Búsqueda binaria en Java

Buscar una matriz para la posición de un valor y clasificar la matriz son dos procesos diferentes. Buscar significa verificar si se encuentra un valor llamado clave en la matriz. Clasificar significa poner todos los valores en la matriz en un orden particular (ascendente o descendente). Si no se ordena una matriz y se requiere una búsqueda, entonces el programa debe comenzar desde el índice cero, luego al índice 1, luego el índice 2, y así sucesivamente, hasta que alcance el índice del valor que está buscando. Si el valor ocurre más de una vez, se debe devolver el primer índice.

Si la matriz se clasifica primero, digamos en orden ascendente, entonces la búsqueda se vuelve fácil. El índice es menor que el índice para el elemento medio, si la clave es menor que el valor del índice medio, o el índice es igual o mayor que el del índice medio, si el valor es igual o mayor que el el del valor del índice medio.

Así que solo divide la matriz en dos. Si el valor se encuentra en el lado izquierdo, no es necesario perder el tiempo buscando el lado derecho; Solo busca el lado izquierdo. Si el valor se encuentra en el lado derecho, no es necesario perder el tiempo buscando en el lado izquierdo; Solo busca el lado derecho. Dado que la matriz ya se clasifica por completo, cuando se llega a cualquier lado, se divide nuevamente en dos, y solo se busca uno de los nuevos pares de lados. De hecho, buscar de esta manera es simplemente dividirse en dos, hasta que se lleve al índice del valor. No se realiza ninguna búsqueda real en términos de escaneo porque la matriz ya está ordenada. Puede haber un ligero movimiento a la derecha, y un poco de movimiento leve a la izquierda en la matriz durante la búsqueda.

Binario implica, dos. Y así, este tipo de búsqueda se llama búsqueda binaria. Hay diferentes órdenes de clasificación: todos los valores en la matriz se pueden clasificar en orden ascendente o orden descendente por completo. Una matriz también se puede clasificar en lo que se conoce como formato de árbol de búsqueda binaria. Esto no es una clasificación completa en orden ascendente o descendente. Sin embargo, la búsqueda de algoritmo binario todavía funciona con este formato.

Este artículo explica la búsqueda binaria de Java. El algoritmo de búsqueda binaria en Java funciona en una matriz que ya está ordenada. Solo se considera la clasificación completa en orden ascendente en este artículo. Este artículo comienza con la ilustración del algoritmo de búsqueda binaria. Luego continúa explicando cómo usar los métodos binarySearch () de la clase de matrices Java.

Contenido del artículo

• Ilustración del algoritmo de búsqueda binaria
• Paquete y clase de Java para búsqueda binaria
• Construyendo la matriz para la búsqueda
• Métodos de búsqueda binarios de la clase de matrices
• Buscando un rango
• Conclusión

Ilustración del algoritmo de búsqueda binaria

Considere la siguiente secuencia de caracteres:

P V D Q S X T H N O

Organización en orden ascendente, la secuencia se convierte en:

D h n o p q s t v x

Hay diez elementos aquí. El conteo de índice comienza desde 0. Cuando el número de elementos es par (e.gramo., 10), el índice para el elemento medio se considera el número de elementos divididos por dos. En este caso, 10/2 es 5. Cuando el número de elementos es impar, el índice para el elemento medio se toma como la parte entera (número entero) del número de elementos divididos por dos.

Hay dos listas arriba. El segundo es la forma ordenada del primero. Suponga que la búsqueda era saber si S estaba presente en la primera lista. La lista primero tendría que clasificarse para tener la segunda lista en el esquema de búsqueda binaria. En la lista ordenada, el índice para la posición media es 5 = 10/2. Esto corresponde al valor, q. La búsqueda luego se detiene para verificar si q es s, el valor buscó. Si es así, entonces la búsqueda se detiene. Si no es así, la búsqueda verifica si S se encuentra menos de Q o desde Q hacia arriba.

En este caso, se encuentra en el rango desde Q hacia arriba, que luego se elige. No se desperdiciará tiempo buscando en la mitad inferior de la lista (matriz). Entonces, esta nueva gama debe dividirse en dos. Este rango consta de 5 elementos. 5/2 = 2 y un 1/2. El elemento medio está en la posición 2 de esta nueva gama. Esto corresponde a T, si el recuento desde cero es comenzar desde Q. El índice real de t es 7.

El rango inferior o izquierdo ahora consta de (Q s), mientras que el nuevo rango superior o derecho ahora consiste en (T V x). Es el nuevo elemento medio, t igual que s, el valor buscado? - No. En el que el rango se encuentra s; ¿Está en el rango inferior, (Q s) o en el rango superior, (T V x)? - Se encuentra en el rango inferior.

Entonces, el rango inferior (Q s) debe dividirse en dos. Cuando esto se hace, el índice medio para este rango corresponde a S (2/2 = 1, ya que Q está en el nuevo índice 0). El índice real para S es 6 (d está en el índice original 0). El índice del valor encontrado debe devolverse.

Clave no encontrada

El valor buscado se llama clave. La lista ordenada en realidad tiene dos indexación como se muestra a continuación:

D	H	norte	O	PAG	Q	S	T	V	X
0	1	2	3	4	5	6	7	8	9
-1	-2	-3	-4	-5	-6	-7	-8	-9	-10

La primera fila de esta tabla tiene la lista ordenada. La segunda fila tiene la indexación normal. La tercera fila tiene un tipo de indexación negativa donde el primer elemento está en el índice -1, el segundo está en el índice -2, el tercero en el índice -3, y así sucesivamente.

Si se encuentra la clave, el algoritmo Java devolverá el índice normal, comenzando a partir de 0. Si no se encuentra la clave, el algoritmo Java devolverá el índice negativo para la posición que la clave habría ocupado (suponiendo que la matriz se extendiera a la derecha por un elemento).

Paquete y clase de Java para búsqueda binaria

El esquema de búsqueda binaria de Java funciona en una matriz que ya está ordenada. Las matrices de clase Java, que se encuentra en el Java.utilizar.* paquete, tiene métodos binarySearch () para buscar binaria una matriz que ya está ordenada. Cada uno de estos métodos devuelve un entero que es un índice normal si se encuentra la clave, o un índice negativo, como se explicó anteriormente, si la clave no se encuentra. Dos de estos métodos son para caracteres.

Construyendo la matriz para la búsqueda

La segunda lista anterior se usará para ilustrar la codificación de búsqueda binaria en Java. La siguiente declaración se puede usar para construir la matriz ordenada:

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;

El esquema de búsqueda binaria de Java funciona en una lista que ya está ordenada.

Métodos de búsqueda binarios de la clase de matrices

La matriz de caracteres anteriores se utilizará en esta sección para ilustración. Los métodos de búsqueda binaria están en la clase de matrices de la Java.utilizar.* paquete. Este paquete debe importarse para que la clase de matrices se utilice.

Todos los métodos de la clase de matrices son métodos estáticos. Esto significa que un objeto no tiene que ser instanciado para ninguno de sus métodos a utilizar. Dos de estos métodos son métodos de búsqueda binarios para caracteres. La sintaxis de uno de los métodos de búsqueda binarios, para caracteres es:

Public static int binarySearch (char [] a, char key)

El siguiente programa busca S que se encuentre:

importar java.utilizar.*;
clase pública THECLASS
public static void main (string [] args)
char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = matrices.BinarySearch (arr, 's');
Sistema.afuera.println (ret);

La salida es 6. El siguiente segmento de código busca b, u y z que no se encuentren cada uno.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret1 = matrices.BinarySearch (arr, 'b');
int ret2 = matrices.BinarySearch (arr, 'u');
int ret3 = matrices.BinarySearch (arr, 'z');
Sistema.afuera.imprimir (ret1); Sistema.afuera.imprimir ("); sistema.afuera.imprimir (ret2);
Sistema.afuera.imprimir ("); sistema.afuera.imprimir (ret3); Sistema.afuera.imprimir(");
Sistema.afuera.println ();

La salida es,

-1 -9 -11

Buscando un rango

La sintaxis para buscar una variedad de caracteres es:

public static int binarySearch (char [] a, int fromIndex, int toIndex, char key)

Fromindex es el índice normal en el que comienza el rango. Toindex es el índice normal justo después del último elemento del rango. El siguiente segmento de código busca la matriz ordenada que comienza desde el índice 3 hasta el índice 7, que es el índice 8. El elemento para el índice 8 no está incluido en el rango.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = matrices.BinarySearch (arr, 3, 8, 's');
Sistema.afuera.println (ret);

La clave es s, y la salida es 6.

Conclusión

Las sintaxis de las matrices para buscar una matriz de tipos primitivos son:

• Public static int binarySearch (byte [] a, clave de byte)
• public static int binarySearch (byte [] a, int fromIndex, int toindex, key de byte)
• Public static int binarySearch (char [] a, char key)
• public static int binarySearch (char [] a, int fromIndex, int toIndex, char key)
• Public static int binarySearch (doble [] a, doble clave)
• public static int binarySearch (double [] a, int fromIndex, int toIndex, doble clave)
• Public static int BinarySearch (Float [] A, Key Float)
• public static int binarySearch (float [] a, int fromindex, int toindex, key float)
• public static int binarySearch (int [] a, int key)
• public static int binarySearch (int [] a, int fromIndex, int toIndex, int key)