class BusquedaBinariaCadena {

   public static void main(String[] argumentos) {
      // Arreglo para probar
      String[] arreglo = { "Chris", "Claire", "Django", "John", "Leon", "Morty", "Rick", "Saul", "Tuco", "Walter" };

      String busqueda = "Morty";

      // Probar primero con la recursiva
      int indiceDelElementoBuscado = busquedaBinariaRecursiva(arreglo, busqueda, 0, arreglo.length - 1);
      System.out.println("[Recursivo] -- El elemento buscado ("
                         + busqueda
                         + ") se encuentra en el index "
                         + indiceDelElementoBuscado);

      // Ahora con la que usa el ciclo while
      indiceDelElementoBuscado = busquedaBinariaConWhile(arreglo, busqueda);
      System.out.println("[Con ciclo While] -- El elemento buscado ("
                         + busqueda
                         + ") se encuentra en el index "
                         + indiceDelElementoBuscado);
   }

   // Busqueda binaria recursiva
   public static int busquedaBinariaRecursiva(String[] arreglo, String busqueda, int izquierda, int derecha) {
      // Si izquierda es mayor que derecha significa que no encontramos nada
      if (izquierda > derecha) {
         return -1;
      }

      // Calculamos las mitades...
      int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
      String elementoDelMedio = arreglo[indiceDelElementoDelMedio];

      // Primero vamos a comparar y luego vamos a ver si el resultado es negativo,
      // positivo o 0
      int resultadoDeLaComparacion = busqueda.compareTo(elementoDelMedio);

      // Si el resultado de la comparación es 0, significa que ambos elementos son iguales
      // y por lo tanto quiere decir que hemos encontrado la búsqueda
      if (resultadoDeLaComparacion == 0) {
         return indiceDelElementoDelMedio;
      }

      // Si no, entonces vemos si está a la izquierda o derecha
      if (resultadoDeLaComparacion < 0) {
         derecha = indiceDelElementoDelMedio - 1;
         return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
      } else {
         izquierda = indiceDelElementoDelMedio + 1;
         return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
      }
   }

   // Busqueda binaria con while
   public static int busquedaBinariaConWhile(String[] arreglo, String busqueda) {

      int izquierda = 0, derecha = arreglo.length - 1;

      while (izquierda <= derecha) {
         // Calculamos las mitades...
         int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
         String elementoDelMedio = arreglo[indiceDelElementoDelMedio];


         // Primero vamos a comparar y ver si el resultado es negativo, positivo o 0
         int resultadoDeLaComparacion = busqueda.compareTo(elementoDelMedio);

         // Si el resultado de la comparación es 0, significa que ambos elementos son iguales
         // y por lo tanto quiere decir que hemos encontrado la búsqueda
         if (resultadoDeLaComparacion == 0) {
            return indiceDelElementoDelMedio;
         }


         // Si no, entonces vemos si está a la izquierda o derecha

         if (resultadoDeLaComparacion < 0) {
            derecha = indiceDelElementoDelMedio - 1;
         } else {
            izquierda = indiceDelElementoDelMedio + 1;
         }
      }
      // Si no se rompió el ciclo ni se regresó el índice, entonces el elemento no
      // existe
      return -1;
   }
}