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;

La forma mas facil de crear un vector en java

Para usar la clase Vector debemos de poner al principio del archivo del código fuente la siguiente sentencia import.

                   import java.util.*;

Cuando creamos un vector u objeto de la clase Vector, podemos especificar su dimensión inicial, y cuanto crecerá si rebasamos dicha dimensión.

                   Vector vector=new Vector(20, 5);

Tenemos un vector con una dimensión inicial de 20 elementos. Si rebasamos dicha dimensión y guardamos 21 elementos la dimensión del vector crece a 25.

Al segundo constructor, solamente se le pasa la dimensión inicial.

                Vector vector=new Vector(20);

Si se rebasa la dimensión inicial guardando 21 elementos, la dimensión del vector se duplica. El programador debe tener cuidado con este constructor, ya que si se pretende guardar un número grande de elementos se tiene que especificar el incremento de la capacidad del vector, si no se quiere desperdiciar inútilmente la memoria el ordenador.

Con el tercer constructor, se crea un vector cuya dimensión inicial es 10.

             Vector vector=new Vector();

La dimensión del vector se duplica si se rebasa la dimensión inicial, por ejemplo, cuando se pretende guardar once elementos.

Añadir elementos al vector

Hay dos formas de añadir elementos a un vector. Podemos añadir un elemento a continuación del último elemento del vector, mediante la función miembro addElement.

        v.addElement("uno");

Podemos también insertar un elemento en una determinada posición, mediante insertElementAt. El segundo parámetro o índice, indica el lugar que ocupará el nuevo objeto. Si tratamos de insertar un elemento en una posición que no existe todavía obtenemos una excepción del tipo ArrayIndexOutOfBounds. Por ejemplo, si tratamos de insertar un elemento en la posición 9 cuando el vector solamente tiene cinco elementos.

Para insertar el string "tres" en la tercera posición del vector v, escribimos lo siguiente:

        v.insertElementAt("tres", 2);

En la siguiente porción de código, se crea un vector con una capacidad inicial de 10 elementos, valor por defecto, y se le añaden o insertan objetos de la clase String.

        Vector v=new Vector();

        v.addElement("uno");

        v.addElement("dos");

        v.addElement("cuatro");

        v.addElement("cinco");

        v.addElement("seis");

        v.addElement("siete");

        v.addElement("ocho");

        v.addElement("nueve");

        v.addElement("diez");

        v.addElement("once");

        v.addElement("doce");

        v.insertElementAt("tres", 2);

Para saber cuantos elementos guarda un vector, se llama a la función miembro size. 

Para saber la dimensión actual de un vector se llama a la función miembro capacity. 

Por ejemplo, en la porción de código hemos guardado 12 elementos en el vector v. La dimensión de v es 20, ya que se ha superado la dimensión inicial de 10 establecida en la llamada al tercer constructor cuando se ha creado el vector v.

             System.out.println("nº de elementos "+v.size());

        System.out.println("dimensión "+v.capacity());

Podemos eliminar todos los elementos de un vector, llamando a la función miembro removeAllElements. O bien, podemos eliminar un elemento concreto, por ejemplo el que guarda el string "tres".

        v.removeElement("tres");

Podemos eliminar dicho elemento, si especificamos su índice.

        

        v.removeElementAt(2);

Acceso a los elementos de un vector

El acceso a los elementos de un vector no es tan sencillo como el acceso a los elementos de un array. En vez de dar un índice, usamos la función miembro elementAt. 

Por ejemplo, v.elementAt(4) sería equivalente a v[4], si v fuese un array.

Para acceder a todos lo elementos del vector, escribimos un código semejante al empleado para acceder a todos los elementos de un array.

        for(int i=0; i<v.size(); i++){

            System.out.print(v.elementAt(i)+"\t");

        }

Existe otra alternativa, que es la de usar las funciones del interface Enumeration. Este interface declara dos funciones pero no implementa ninguna de ellas. Una Enumeration nos permite acceder a los elementos de una estructura de datos de forma secuencial.

       public interface Enumeration {

              boolean hasMoreElements();

             Object nextElement();

            }

La función miembro elements de la clase Vector devuelve un objeto de la clase VectorEnumerator que implementa el interface Enumeration y tiene que definir las dos funciones hasMoreElements y nextElement.

 final class VectorEnumerator implements Enumeration {

    Vector vector;

    int count;

    VectorEnumerator(Vector v) {

        vector = v;

        count = 0;

    }

    public boolean hasMoreElements() {

        //...

    }

    public Object nextElement() {

        //...

    }

}

El objeto enum devuelto por la función miembro elements es de la clase VectorEnumerator, sin embargo no podemos escribir:

        VectorEnumerator enum=v.elements();

porque VectorEnumerator no es una clase pública. Como podemos ver en su definición, no tiene la palabra reservada public delante de class. Sin embargo, podemos guardar un objeto de la clase VectorEnumerator en una variable enum del tipo Enumeration, por que la clase implementa dicho interface.

 Enumeration enum=v.elements();

        while(enum.hasMoreElements()){

            System.out.print(enum.nextElement()+"\t");

        }

Desde el objeto enum devuelto por la función miembro elements de la clase Vector llamamos a las funciones miembro hasMoreElements y nextElement de la clase VectorEnumerator.

La función hasMoreElements devuelve true mientras haya todavía más elementos que se puedan acceder en el vector v. Cuando se ha llegado al último elemento del vector, devuelve false. 

La función nextElementdevuelve una referencia al próximo elemento en la  estructura de datos. Esta función devuelve una referencia a un objeto de la clase base Object, que el programador precisará en ciertos casos, como veremos más abajo, promocionar (casting) a la clase adecuada.

Para buscar objetos en un vector se puede usar una Enumeration y hecer una comparación elemento por elemento mediante equals, tal como vemos en le siguiente código:

        Enumeration enum=v.elements();

        while(enum.hasMoreElements()){

            String elemento=(String)enum.nextElement();

            if(elemento.equals("tres")){

                System.out.println("Encontrado tres");

                break;

            }

        }

Podemos usar alternativamente, la función miembro contains para este propósito.

        if(v.contains("tres")){

            System.out.println("Encontrado tres");

        }

Lenguaje C

¿Qué es el lenguaje de programación C?

C es un lenguaje de programación de propósito general que ofrece economía sintáctica, control de flujo y estructuras sencillas y un buen conjunto de operadores. No es un lenguaje de muy alto nivel y más bien un lenguaje pequeño, sencillo y no está especializado en ningún tipo de aplicación. Esto lo hace un lenguaje potente, con un campo de aplicación ilimitado y sobre todo, se aprende rápidamente. En poco tiempo, un programador puede utilizar la totalidad del lenguaje.

Este lenguaje ha sido estrechamente ligado al sistema operativo UNIX, puesto que fueron desarrollados conjuntamente. Sin embargo, este lenguaje no está ligado ningún sistema operativo ni a ninguna máquina concreta. Se le suele llamar lenguaje de programación de sistemas debido a su utilidad para escribir compiladores y sistemas operativos, aunque de igual forma se puede desarrollar cualquier tipo de aplicación.

¿De dónde proviene la base de C?

La base del C proviene del BCPL, escrito por Martin Richards, y del B escrito por Ken Thompson en 1970 para el primer sistema UNIX en un DEC PDP-7. Estos son lenguajes sin tipos, al contrario que el C que proporciona varios tipos de datos.

Tipos de datos

Los tipos que ofrece son:

Caracteres, números enteros y en coma flotante, de varios tamaños. Además se pueden crear tipos derivados mediante la utilización de punteros, vectores, registros y uniones.

Primer compilador de C

El primer compilador de C fue escrito por Dennis Ritchie para un DEC PDP-11 y escribió el propio sistema operativo en C.

¿Cómo trabaja el lenguaje C?

C trabaja con tipos de datos que son directamente tratables por el hardware de la mayoría de computadoras actuales, como son los caracteres, números y direcciones. Estos tipos de datos pueden ser manipulados por las operaciones aritméticas que proporcionan las computadoras. No proporciona mecanismos para tratar tipos de datos que no sean los básicos, debiendo ser el programador el que los desarrolle. Esto permite que el código generado sea muy eficiente y de ahí el éxito que ha tenido como lenguaje de desarrollo de sistemas. No proporciona otros mecanismos de almacenamiento de datos que no sea el estático y no proporciona mecanismos de entrada ni salida. Ello permite que el lenguaje sea reducido y los compiladores de fácil implementación en distintos sistemas. Por contra, estas carencias se compensan mediante la inclusión de funciones de librería para realizar todas estas tareas, que normalmente dependen del sistema operativo.