#desafiodrk4

Desafío DRK 4

Enunciado

Dado un array con enteros que originalmente estaba ordenado y luego fue rotado circularmente una cantidad arbitraria y desconocida de veces. Diseñar un algoritmo capaz de encontrar el menor entero en complejidad temporal menor que O(n).

Detalles

  • Se recibe una arreglo (array) de enteros que estaba ordenado (el menor elemento estaba en la primera posición) y fue rotado.
  • La rotación circular implica que los elementos que caen fuera del array al arrastrarlos en una dirección se insertan automáticamente por el extremo opuesto.
  • La secuencia ordenada no comienza necesariamente en 1.
  • No es necesariamente una serie consecutiva.
  • La entrada siempre es válida según la reglas del enunciado.

Videos

Ejemplos

Entrada

[3, 4, 5, 7, 8, 1, 2]

Resultado: 1

Entrada

[20, 30, 40, 10]

Resultado: 10

Entrada

[5, 6, 7, 8]

Resultado: 5

Entrada

[4, 5, 1, 2, 3]

Resultado: 1

Cómo enviar respuestas

Para enviar respuestas largas o que contengan código (no sólo para este desafío sino en las redes sociales en general) se puede utilizar:

Luego pegar la URL en un comentario del video o enviar un mail.

Fuente

Cracking the code interview - Gayle Laakmann McDowel

La fuente de referencia es donde recuerdo haber encontrado el enunciado. Pero estos ejercicios se repiten en forma masiva por lo que la fuente citada no necesariamente es el autor.