Consideremos dos conjuntos de $D=\{ d_1, d_2, \dots, d_n\}$ e $E=\{ e_1, e_2, \dots, e_m \}$ y considere la posibilidad de otra variable $K \geq 0$. La demostración de que podemos responder en el tiempo $O((n+m) \lg (n+m))$ la siguiente pregunta: Es que hay un par de números de $a,b$ donde $a \in D, b \in E$ tal que $|a-b| \leq K$?
El algoritmo debe responder a la anterior pregunta con un SÍ o NO. Describir el algoritmo, mostrar su corrección y muestran que su tiempo de complejidad es $O((n+m) \lg (n+m))$.
Escribí el siguiente algoritmo:
int binary_search(int A[], int key, int low, int high, int K)
{
if (high < low) return 0;
else{
int mid=low+floor((high-low)/2);
if (A[mid]<key-K) return binary_search(A, key, mid+1, high);
else if (A[mid]>k+key) return binary_search(A, key, low, mid-1 );
else return mid;
}
}
Algorithm(D,E,K) {
HeapSort(E);
low=1;
high=m;
i=1;
p=0
while (i<=n and p==0){
p=binary_search(E, D[i], low, high, K );
i++;
}
if (p==0) printf("NO \n");
else printf("YES \n");
}
Podemos probar la exactitud de binary_search de la siguiente manera, ¿verdad?
Caso Base:
Vamos a suponer que tenemos una matriz de tamaño 1.
Entonces se mantiene $low=high=mid$.
Si el si-declaración sostiene luego llamamos a la función binary_search(A, clave, baja+1, bajo) y desde $high<low$, la función devolverá $0$. El resultado es justo, porque sólo tenemos un elemento que no satisface la propiedad deseada , estamos mirando adelante para otro elemenent,pero ya que no hay otro, significa que el elemento no existe.
De manera similar para el caso cuando la persona-si-statament sostiene.
Además, no importa que sie la matriz, si el elemento que estamos buscando tiene la propiedad deseada, luego el otro-declaración de retenciones,de manera que el algoritmo devuelve la posición correcta.
Inducción hipótesis:
Suponemos que binary_search da el resultado correcto para matrices con el tamaño de la $<n$.
Inducción paso:
Ahora consideramos una matriz de tamaño $n$. Si el si - o bien-si la declaración contiene, llamamos a la binary_search para una matriz de tamaño $<n$, por lo que desde la inducción de la hipótesis de que sabemos que vamos a tener el resultado correcto.
De lo contrario, vamos a tener el resultado correcto, desde la base de los casos.
Pero ¿cómo podemos demostrar la corrección del algoritmo de Algorithm?
EDIT: eso es lo Que pensé cuando escribí el siguiente algoritmo:
Podemos ordenar la matriz E en fin de llamar la binary_search que volverá $0$ si no hay dos elementos $a,b$ de % de $D,E$ tal que $|a-b| \leq K$ o de la posición en la que el elemento de $E$, lo que nos resta con un elemento de D y convertirse en una diferencia por valor absoluto es menor o igual a $K$. Así que si el binary_search devuelve 0, el algoritmo devolverá N0, de lo contrario volverá en SÍ.
