tipos - Algoritmo para encontrar si hay alguna i para que la matriz[i] sea igual a i
operaciones con matrices (8)
Piense en una búsqueda binaria como buscar una palabra en el diccionario. Puede comenzar abriendo el libro exactamente en el centro del diccionario y ver si la palabra en la parte superior de la página es anterior, posterior o igual a la palabra que está buscando. Si es después, divide la última mitad del diccionario en dos y marca el medio de esa mitad. Después de mirar la parte superior de la página, ha reducido el área en la que está buscando dentro de una cuarta parte del diccionario. Continúe este proceso hasta que encuentre que la palabra está en algún lugar de la página que está mirando. Luego usa un proceso similar para encontrar la palabra en esa página.
Este proceso no es O (n) porque no tenía que mirar cada palabra en cada página, incluso en el peor de los casos. Es O (log n) porque con cada paso fue capaz de eliminar aproximadamente la mitad del diccionario que no contenía la palabra que estaba buscando.
Editar
Lo siento, he entendido mal el problema original.
En este caso, la clave es reconocer el llamado "principio del pozo de los pidgeon", que establece que solo puede colocar tantos pidgeons en los agujeros como que tenga agujeros para encajarlos (déjelo en la academia para que aparezca). ¡con un nombre para una idea tan simple!)
Considere el siguiente caso:
0 1 2 3 4 5 6
Aquí, todos los array[i] son iguales a i , de modo que cuando comiences tu búsqueda binaria, tendrás inmediatamente una respuesta positiva.
Ahora tomemos un número desde abajo:
0 1 3 4 5 6
Cuando haces tu búsqueda binaria, encontrarás esa array[3] > 3 , y puedes deducir correctamente que ningún valor por encima de ese punto de pivote podría hacer una array[i] == i . Esto se debe a que la lista está ordenada y es única, por lo que no puede terminar con combinaciones como estas:
0 1 3 4 5 5 6
0 1 3 4 6 5 7
Una vez que se determina que la array[i] es mayor que i , simplemente no hay números suficientes entre i y cualquier n dado para permitir que el siguiente elemento de la matriz se acerque más a i . Del mismo modo, si determina que la array[i] es menor que i , no tiene suficientes "huecos" disponibles para "alcanzar" a i cuando mira hacia el comienzo de la matriz.
Por lo tanto, en cada paso, puede eliminar correctamente la mitad de la matriz y, al igual que buscar en un diccionario, determinar si alguna array[i] == i en O (log n) tiempo.
Tengo una tarea de mi profesor de CS:
Encuentra, en el tiempo O (logn), si en una matriz preordenada dada de enteros distintos hay un índice i para que la matriz [i] = i. Demuestre que el tiempo es O (logn).
Actualización: los enteros pueden ser negativos, 0 o positivos.
Bien, entonces he luchado un poco con esto. Mi idea es esta:
Usando la búsqueda binaria, solo podemos estar seguros de que no existe tal valor a la izquierda del elemento medio si array [mid] <= startindex, donde mid es el índice del elemento medio, y startindex es el comienzo de la matriz.
La regla correspondiente para la mitad derecha de una matriz es esa matriz [mid]> = startindex + numel, donde las variables como arriba y numel es la cantidad de elementos a la derecha de la mitad.
Esto no parece ser O (logn), ya que en el peor de los casos tengo que repetir todo el proceso, ¿verdad? ¿Puede alguien darme una propina en la dirección correcta aquí, o decirme que esto funciona?
¿Alguna idea de cómo podría probar esto formalmente? No estoy pidiendo una respuesta definitiva, más ayuda para hacerme entender.
Cª:
int _solve_prob_int(int depth, int start, int count, int input[])
{
if(count == 0)
return 0;
int mid = start + ((count - 1) / 2);
if(input[mid] == mid)
return 1;
if(input[mid] <= start && input[mid] >= start + count)
return 0;
int n_sub_elleft = (int)(count - 1) / 2;
int n_sub_elright = (int)(count) / 2;
if(input[mid] <= start)
return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
if(input[mid] >= start + count)
return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input);
return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) ||
_solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
}
Un caso de prueba:
Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 :
Start: 0, count: 12, mid: 5 value: 6
Start: 0, count: 5, mid: 2 value: 3
Start: 0, count: 2, mid: 0 value: 1
Start: 1, count: 1, mid: 1 value: 2
Start: 3, count: 2, mid: 3 value: 4
Start: 4, count: 1, mid: 4 value: 5
Start: 6, count: 6, mid: 8 value: 9
Start: 6, count: 2, mid: 6 value: 7
Start: 7, count: 1, mid: 7 value: 8
Start: 9, count: 3, mid: 10 value: 11
Start: 9, count: 1, mid: 9 value: 10
Start: 11, count: 1, mid: 11 value: 12
Lo anterior es mi programa ejecutado con algunos resultados de acuerdo con la búsqueda. Con una lista del 1 al 12, gira alrededor del índice 5, determina que podría haber un valor entre 0-4 en los índices 0-4. También determina que podría haber un valor entre 6-11 en los índices 6-11. Por lo tanto, procedo a buscarlos a ambos. ¿Esto esta mal?
Trataré de no dar la respuesta, pero señalaré algunas observaciones:
Al examinar el elemento medio, hay 3 casos. El primero es, por supuesto, ese conjunto [i] == i, en cuyo caso el algoritmo finaliza. En los otros dos casos, podemos descartar el elemento en sí mismo, así como aproximadamente la mitad de la entrada.
Ahora, si la matriz [i]> i, ¿es posible que el índice de la matriz (i) se "ponga al día" con los valores de la matriz a medida que avanzamos hacia la derecha? Tenga en cuenta las distintas propiedades ordenadas de los valores de la matriz.
Tu intuición es correcta para utilizar la búsqueda binaria; tu análisis no es Recuerde que es una lista ordenada, por lo que en la condición de búsqueda binaria, necesita buscar un MÁXIMO de entradas de registro (n).
Este es un problema de búsqueda binaria con clave no especificada . En la pregunta de OP, ¡la clave está en medio! Eso es todo, busca el elemento medio en cada subcampo.
Pseudocódigo de la solución que utiliza la búsqueda binaria:
while (low and high don''t meet)
mid = (low + high) / 2
if (arr[mid] < mid)
high = mid - 1
else if (arr[mid] > mid)
low = mid + 1
else // we found it!
return mid;
// end while
return -1; // indicates there is no such i
ya que la matriz A está ordenada. A [i]> = A [i-1] +1 => A [i] -i> = A [i-1] - (i-1), deje B [i] = A [i] -i, B [] es una matriz ordenada que se puede buscar en B [x] == 0 en tiempo real mediante búsqueda binaria.
Array B[i] = A[i]-i NO se puede ordenar incluso si A [i] está ordenado pero tiene duplicados:
Considera este ejemplo:
yo: 0 1 2 3 4
A: 1 1 2 4 4B [0] = A [0] -0 = 1, B [1] = A [1] -1 = 0, ...
B: 1 0 0 1 0
public static int fixedPoint(int[] array, int start, int end) {
if (end < start || start < 0 || end >= array.length) {
return -1;
}
int midIndex = start +(end-start)/ 2;
int midValue = array[midIndex];
if (midValue == midIndex) {//trivial case
return midIndex;
}
// if there are duplicates then we can''t conclude which side (left or right) will
// have the magic index. so we need to search on both sides
//but, we can definitely exclude few searches.
// take the example of the array :
// 0 1 2 3 4 5 6 7 8 9 10 -> indices
// -10, -5, 2, 2, 2, 3(midVal, midIndex = 5), 4, 7, 9, 12, 13 -> array element
// here, midValue < midIndex, but we can''t say for sure which side to exclude
// as you can see there are two such magic indices. A[2] = 2 and A[7] = 7. so
// we need to search both sides
// since midValue < midIndex, then we can be sure that between index can''t be
// between index number midValue and midIndex-1
/* Search left */
int leftIndex = Math.min(midIndex - 1, midValue);
int left = fixedPoint(array, start, leftIndex);
if (left >= 0) {
return left;
}
/* Search right */
int rightIndex = Math.max(midIndex + 1, midValue);
int right = fixedPoint(array, rightIndex, end);
return right;
}
public static int fixedPoint(int[] array) {
return fixedPoint(array, 0, array.length - 1);
}
El entero es distintivo y ordenado.
Dado i tal que array[i] = i tienes array[i] - i = 0 .
Para cada j <i tienes array[j] - j <= 0 y para j> i tienes array[j] - j >= 0 porque j varían de 1 en cada paso pero el array [j] varía de al menos 1 (números distintos y ordenados).
Entonces, a la izquierda, es <=0 a la derecha, es >= 0 .
Usando la dicotomía, puede encontrar fácilmente la posición correcta en O(log n) .
O(n) ..