Ordenamiento Binario

La búsqueda binaria consiste en emplear "divide y vencerás" para, dividiendo el problema por la mitad, dirigirse a la izquierda o derecha dependiendo de la comparación de la palabra a encontrar con el elemento del medio, y así sucesivamente, hasta encontrar la palabra a buscar. Tened en cuenta que la implementación más sencilla del algoritmo supone invocar recursivamente al método buscar (search).

Se pide: Codificar el método search que realiza la búsqeda binaria. Se puede descargar un esqueleto de esta clase aquí BinarySearch.java.

public void int compareTo(String a)
Dados dos String:
String cadena1
String cadena2

El método compareTo funciona de la siguiente forma: cadena1.compareTo(cadena2)

devuelve un número negativo si cadena1 < cadena2
devuelve un número positivo si cadena1 > cadena2
devuelve 0 si cadena1 = cadena2

ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden.

Complejidad:
Insertar elementos en un árbol binario de búsqueda tiene una complejidad O(log n). Entonces, agregar n elementos a un árbol cualquiera da como resultado una complejidad O(n log n). Además, recorrer los elementos del árbol en inorden tiene complejidad O(n).

Características:
Tiene un buen rendimiento.
Es estable (no cambia el orden relativo de elementos iguales).
No requiere espacio de almacenamiento extra.
Puede ordenar listas tal cual las recibe.