Como hacer una búsqueda binaria en arrays ordenados en Java

Primero que nada hay que saber que es un array:

Un array es una estructura de datos que nos permite almacenar una gran cantidad de datos de un mismo tipo. El tamaño de los arrays se declara en un primer momento y no puede cambiar en tiempo de ejecución como puede producirse en otros lenguajes.

Búsqueda binaria en arrays ordenados

Para buscar un elemento en un array ordenado se puede aplicar la técnica de la búsqueda binaria.

El conjunto de búsqueda se delimita por dos posiciones: el límite inferior y el límite superior. 

El algoritmo empieza la búsqueda por el elemento que está almacenado en la mitad del conjunto de búsqueda. Si el elemento almacenado en la mitad del conjunto es mayor que el valor que se busca, entonces continúa la búsqueda en la primera mitad. Si el elemento almacenado en la mitad del conjunto es menor que el valor que se busca, entonces continúa la búsqueda en la segunda mitad. Si el elemento almacenado en la mitad del conjunto es igual que el valor que se busca, finaliza el proceso. En cada comparación, el algoritmo reduce el conjunto de búsqueda a la mitad. Si durante las sucesivas reducciones del conjunto de búsqueda el límite inferior es mayor que el límite superior, entonces el valor que se busca no está en el array y finaliza el proceso.

En este ejemplo el conjunto de búsqueda tiene 10 elementos, el límite inferior coincide con el primer elemento del array y el límite superior con el último elemento del array.

Si se aplica la búsqueda binaria para buscar el número 18, el algoritmo realiza las siguientes reducciones del conjunto de búsqueda.

Cuando se busca el número 18 en el array, en la primera iteración se compara el valor almacenado en la mitad con el 18. La mitad es la posición 4 y almacena un 10. Como 18 es mayor que 10, se descarta la primera mitad del conjunto de búsqueda y el límite inferior se hace igual a la mitad + 1. Ahora, el límite inferior es 5 y la nueva mitad es 7. Los valores del array que se han descartado en esta iteración se han tachado.

Una vez más, se compara el 18 con el valor almacenado en la mitad, que es 16. Como 18 es mayor que 16, se descarta la primera mitad del conjunto de búsqueda y el límite inferior se hace igual a la mitad + 1. Ahora, el límite inferior es 8 y la nueva mitad es 8. En la siguiente iteración se compara el valor almacenado en la posición central con el 18 y finaliza el algoritmo.

En este ejemplo, el algoritmo de búsqueda binaria ha realizado tres comparaciones para encontrar el número 18 en el array.

Durante el proceso de división del conjunto de búsqueda se modifica el valor del límite inferior o del límite superior, dependiendo de si el número que se busca está en la primera mitad o en la segunda mitad. Si durante este proceso el límite inferior es mayor que el límite superior, entonces el algoritmo finaliza porque el número que se busca no está en el array.

El siguiente programa utiliza el algoritmo de búsqueda binaria para buscar un número entre cero y 100 en un array de números ordenados.

public class BusquedaBinaria {

public static void main(String[] args) {

int[] numeros = {1,2,3,4,6,7,8,9,10,16,17,19,45,59,60,68,74,85};

int mitad;

int limiteInferior = 0;

int limiteSuperior = numeros.length - 1;

int numeroBusqueda = 45;

boolean encontrado = false;

while ((limiteInferior <= limiteSuperior) && (!encontrado)) {

mitad = (limiteInferior + limiteSuperior) / 2;

if (numeros[mitad] == numeroBusqueda) {

encontrado = true; // ¡encontrado!

}

else if (numeros[mitad] > numeroBusqueda) {

limiteSuperior = mitad - 1; // buscar en la primera mitad

} else {

limiteInferior = mitad + 1; // buscar en la segunda mitad

}

}

if (encontrado)

System.out.println("He encontrado el número");

else

System.out.println("No he encontrado el número");

}

}

Expresiones en Java

    ¿Que es una expresión en Java?

Una expresión es una combinación de variables, operadores y llamadas de métodos construida de acuerdo a la sintaxis del lenguaje que devuelve un valor. 

¿Qué permite las expresiones en Java?

Una expresión permite realizar operaciones entre valores utilizando distintos operadores. Las expresiones son útiles para representar las fórmulas matemáticas que se utilizan para realizar cálculos.

En Java se pueden definir expresiones tan complejas como sea necesario.

Por ejemplo: para convertir una temperatura de grados Fahrenheit a

Centígrados se utiliza la fórmula:

C = ((F – 32) * 5) / 9

En este ejemplo C representa la temperatura en grados centígrados y F en grados Fahrenheit. La fórmula en Java, utilizando las variables centigrados y fahrenheit de tipo double.

centigrados = ((fahrenheit – 32.0) * 5.0)) / 9.0;

Toda la expresión se evalúa a un valor. El orden de los cálculos depende del orden de prioridad de los operadores: primero los operadores unarios, después los multiplicativos, de izquierda a derecha, después los operadores aditivos, de izquierda a derecha, después los operadores de relación y por último los operadores de asignación.

Por ejemplo: la expresión x = -3 + 2 * 4 – 12 / 6 + 5 se calcula en el orden siguiente:

Primero se aplica el operador unario (-) a 3 y se obtiene -3. A continuación se evalúan los operadores multiplicativos de izquierda a derecha. Se calcula el producto de 2 * 4 y se obtiene 8, después se divide 12 / 6 y se obtiene 2.

Al finalizar estas operaciones la expresión queda x = -3 + 8 – 2 + 5. Por último, se evalúan los operadores aditivos de izquierda a derecha y se obtiene 8.

Cuando se desea modificar el orden de prioridad de los operadores es necesario utilizar paréntesis para indicar el orden de evaluación. Por ejemplo, al calcular el valor de y = -3 + 2 * (14 – 2) / 6 + 5 se obtiene 6.

Expresiones aritmético-lógicas

Una expresión aritmético-lógica devuelve un valor lógico verdadero o falso.

En este tipo de expresiones se utilizan operadores aritméticos, operadores relacionales y de igualdad. Por ejemplo, una expresión lógica puede ser:

(10 – 2) > (5 – 3)

En este ejemplo la expresión aritmético-lógica es verdadera porque el lado derecho de la expresión es mayor que el lado izquierdo.

En una expresión aritmético-lógica se pueden combinar varias expresiones con operadores lógicos. La precedecencia de los operadores lógicos es menor que la de los operadores relacionales, por lo que primero se evalúan las desigualdades y después los operadores lógicos. El orden de prioridad de los operadores lógicos es el siguiente: primero la negación, después el Y lógico y por último el O lógico. La prioridad de los operadores de asignación es la menor de todas.

Por ejemplo: la expresión 3 + 5 < 5 * 2 || 3 > 8 && 7 > 6 – 2 se evalúa en el orden siguiente.

Primero se evalúan las expresiones aritméticas y se obtiene la expresión lógica 8 < 10 || 3 > 8 && 7 > 4. A continuación se evalúan los operadores relacionales y se obtiene true || false && true. Ahora se evalúa el operador Y lógico con los operandos false && true y se obtiene false.

Por último, se evalúa el operador O lógico con los operandos true || false y se obtiene true, el valor final de la expresión.

Los operadores lógicos && y || se evalúan por cortocircuito. Esto significa que al evaluar a && b, si a es falso, no es necesario evaluar b porque la expresión es falsa. De forma similar, al evaluar a || b, si a es verdadero, no es necesario evaluar b porque la expresión es verdadera.

Variables y valores en Java

                                                              

                                                          ¿Qué es una variable?

Una variable es un espacio de la memoria del ordenador a la que asignamos un contenido que puede ser un valor numérico (sólo números, con su valor de cálculo) o alfanumérico (sólo texto o texto con números). Cada variable tiene un único nombre el cual no puede ser cambiado. Dos o más variables pueden tener el mismo contenido, pero no el mismo nombre. El nombre de una variable comenzará siempre por una letra, pudiendo contener a continuación tanto letras como números.

Variables en Java

Un programa Java utiliza variables para almacenar valores, realizar cálculos, modificar los valores almacenados, mostrarlos por la consola, almacenarlos en disco, enviarlos por la red, entre otros. Una variable almacena un único valor.

Definición

Una variable se define por un nombre, un tipo y el rango de valores que puede almacenar.

El nombre de una variable permite hacer referencia a ella. Este nombre debe cumplir las reglas aplicables a los identificadores. El tipo indica el formato de los valores que puede almacenar la variable: cadenas de caracteres, valores lógicos, números enteros, números reales o tipos de datos complejos. El rango indica los valores que puede tomar la variable.

Por ejemplo: una variable de tipo número entero, con nombre mesNacimiento puede almacenar valores positivos y negativos, lo que no tiene sentido cuando se trata de meses del año. El rango válido para esta variable sería de 1 a 12.

Para declarar una variable en Java se indica el tipo y su nombre.

int mesNacimiento;

En este ejemplo se indica que la variable es de tipo entero (int) y su nombre es mesNacimiento. Una vez declarada una variable, se puede utilizar en cualquier parte del programa referenciándola por su nombre.

Para almacenar un valor en una variable se utiliza el operador de asignación y a continuación se indica el valor, por ejemplo 2.

mesNacimiento = 2;

A partir de este momento la variable mesNacimiento almacena el valor 2 y cualquier referencia a ella utiliza este valor. Por ejemplo, si se imprime el valor de la variable por la consola, muestra el valor 2.

System.out.print(mesNacimiento);

Java permite declarar e inicializar una variable en una sola sentencia.

int diaNacimiento = 20;

int mesNacimiento = 3;

En este ejemplo se declaran las variables diaNacimiento con el valor 20 y mesNacimiento con valor 3.

Si se declara una constante, entonces se debe utilizar el delimitador final y es necesario indicar su valor. En la siguiente declaración se define el valor de la constante pi de tipo double para almacenar un número real.

final double PI = 3.1415926536;

Es conveniente utilizar nombres apropiados para las variables. El nombre de una variable debe indicar para qué sirve. El nombre de una variable debe explicarse por sí mismo para mejorar la legibilidad del programa.

Si se desea declarar más de una variable a la vez se deben separar las  variables en la sentencia de la declaración.

int dia=20, mes=2, año=2020;

En este ejemplo se declaran las variables enteras dia, mes y año. La variable día se inicializa con el valor 20, mes con 2 y año con 2020.

La siguiente declaración es equivalente a la anterior:

int dia=20;

int mes=2;

int año=2020;