Foro de elhacker.net

El siguiente codigo se ejecuta en orden lineal con respecto al tamaño del arreglo A, mi pregunta es cómo hacer dicho codigo más eficiente, digamos O(log n), la idea que tengo es hacer busqueda binaria, es decir, dividir A a la mitad ((i-1) / 2) y buscar en cada mitad.
Pero:

• Si encuentro un i > 0 en la primera mitad deberia buscar en la segunda. (podria existir un i mayor)
• Si no encuentro un i > 0 en la segunda mitad debería buscar en la primera si no lo hice antes. (ya que podria existir un i > 0)

Por lo que sigue siendo O(n) en el peor caso, quiza no sea posible implementarlo en O(log n)

/* A[1..n] esta ordenado de menor a mayor
 * Devuelve el mayor indice i' menor o igual a i tal que A[i'] <= c
 * o cero si no se encuentra. Cota superior asintotica: O(n)
 */
void buscarIndice(const uint* A, uint &i, const uint c) {
	while (i > 0 && A[i] > c)
		i--;
}
 

El siguente codigo es O(n^2), lo que si es seguro es que como A está ordenado es posible implementarlo en O(n log n) (La demostración queda a cargo del lector) ¿Alguna idea de por donde empezar?

for (uint j = 1; j <= n; j++) {
	uint i = j; // No es ortodoxo modificar j
	buscarIndice(A, i, c);
	hacerAlgoUtilCon(i);
}

Creo que lo que buscas es esto:

kPRA0W1kECg

Lo consegui:

uint buscarIndice(const uint* A, uint i, uint c) {
	uint l = 1, r = i;
	while (l <= r) {
		uint m = (l + r) / 2;
		if (A[m - 1] <= c) {
			if (A[m] <= c)
				l = m + 1;
			else
				return m;
		} else
			r = m - 1;
	}
	return 0;
}
 

BuscarIndice no... la función debe llamarse como lo que es una: BusquedaBinaria o dicotomica.

Es posible optimizarla un poco más, si necesitas hacer muchas más búsquedas sobre el mismo array ordenado.

Para ello antes de devolver, recuerdas el índice y el valor que acabas de buscar.
En la siguiente llamada, al entrar comparas si la entrada es menor mayor o igual que la guardada antes:
---- Si es menor, el espacio de búsqueda se limita a "Min - indicerecordado-1"
---- Si es mayor el espacio de búsqueda se limita a "indicerecordado+1 - max"
---- Si es igual, devuelves el indicerecordado.