¿Cuál de las siguientes es la recurrencia correcta para el peor de los casos de búsqueda binaria?
(A) T(n) = 2T(n/2) + O(1) y T(1) = T(0) = O(1)
(B) T(n) = T(n-1) + O (1) y T(1) = T(0) = O(1)
(C) T(n) = T(n/2) + O(1) y T(1) = T(0) = O( 1)
(D) T(n) = T(n-2) + O(1) y T(1) = T(0) = O(1)
Respuesta: (C)
Explicación: La siguiente es una implementación típica de la búsqueda binaria .
// Searches x in arr[low..high]. If x is present, then returns its index, else -1 int binarySearch(int arr[], int low, int high, int x) { if(high >= low) { int mid = low + (high - low)/2; if (x == arr[mid]) return mid; if (x> arr[mid]) return binarySearch(arr, (mid + 1), high); else return binarySearch(arr, low, (mid -1)); } return -1; }
En la búsqueda binaria, primero comparamos el elemento dado x con el medio de la array. Si x coincide con el elemento central, devolvemos el índice central. De lo contrario, recurrimos para la mitad izquierda de la array o la mitad derecha de la array.
Entonces la recurrencia es T(n) = T(n/2) + O(1)
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