Sea A una array de 31 números que consta de una secuencia de 0 seguida de una secuencia de 1. El problema es encontrar el índice i más pequeño tal que A[i] sea 1 sondeando el número mínimo de ubicaciones en A. El peor número de sondeos realizados por un algoritmo óptimo es________.
Nota: Estas preguntas aparecieron como tipo de respuesta numérica.
(A) 2
(B) 3
(C) 4
(D) 5
Respuesta: (D)
Explicación: La mejor manera de resolver este problema es mediante la búsqueda binaria . Busque en la array ordenada dividiendo repetidamente el intervalo de búsqueda por la mitad. Comience con un intervalo que cubra todo el arreglo. Si el valor de la clave de búsqueda es menor que el elemento en el medio del intervalo, reduzca el intervalo a la mitad inferior. De lo contrario, redúcelo a la mitad superior.
Encuentra el elemento medio
- ¿Es medio = 1?
- ¿Es mid >1? (no es posible aquí)
- ¿Es medio < 1?
Proceda en consecuencia, el peor de los casos de este problema será 1 al final de la array, es decir, 00000…..1 O 1…….0000. Tomará log n time en el peor de los casos.
n=31, por lo tanto log 2 31 = 5.
Por lo tanto, la opción D es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA