Algoritmos | Buscando | Pregunta 3

Dada una array ordenada de enteros, ¿cuál puede ser la complejidad de tiempo mínima en el peor de los casos para encontrar el techo de un número x en una array determinada? El techo de un elemento x es el elemento más pequeño presente en la array que es mayor o igual que x. El techo no está presente si x es mayor que el elemento máximo presente en la array. Por ejemplo, si la array dada es {12, 67, 90, 100, 300, 399} y x = 95, entonces la salida debería ser 100.
(A) O(LogLogn)
(B) O(n)
(C) O (Iniciar sesión)
(D) O(Iniciar sesión * Iniciar sesión)

Respuesta: (C)
Explicación: Modificamos la búsqueda binaria estándar para encontrar el techo. La complejidad temporal T(n) se puede escribir como

T(n) <= T(n/2) + O(1)

La solución de la recurrencia anterior se puede obtener mediante el método maestro. Cae en el caso 2 del Método Maestro. La solución es O (Iniciar sesión).

#include<stdio.h>

/* Función para obtener el índice del techo de x en arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
int mid;

/* Si x es menor o igual que el primer elemento,
devuelve el primer elemento */
if(x <= arr[low])
return low;

/* Si x es mayor que el último elemento, devuelve -1 */
if(x > arr[high])
return -1;

/* obtiene el índice del elemento medio de arr[low..high]*/
mid = (low + high)/2; /* bajo + (alto – bajo)/2 */

/* Si x es igual que el elemento del medio, devuelve mid */
if(arr[mid] == x)
return mid;

/* Si x es mayor que arr[mid], entonces arr[mid + 1]
es el techo de x o el techo está en arr[mid+1…high] */
else if(arr[mid] < x)
{
if (medio + 1 <= alto && x <= arr[medio+1])
return medio + 1;
else
return ceilSearch(arr, mid+1, high, x);
}

/* Si x es menor que arr[mid], entonces arr[mid]
es el techo de x o el techo está en arr[mid-1…high] */
else
{
if(mid – 1 >= low && x > arr [medio-1])
volver medio;
else
return ceilSearch(arr, low, mid – 1, x);
}
}

/* Programa controlador para comprobar las funciones anteriores */
int main()
{
int arr[] = {1, 2, 8, 10, 10, 12, 19};
int n = tamaño de (arr)/tamaño de (arr [0]);
entero x = 20;
int index = ceilSearch(arr, 0, n-1, x);
if(index == -1)
printf(«El techo de %d no existe en el arreglo «, x);
else
printf(«el techo de %d es %d», x, arr[index]);
getchar();
devolver 0;
}

Cuestionario de esta pregunta