Problema: Búsqueda en Array

[j retirado]

Problema: Se recibe un arreglo X de numeros enteros definido en [0, n-1] y un entero x.
Se quiere determinar si existen i, j en [0, n-1] tal que X + X[j] = x.
Diseñe un algoritmo para resolver el problema cuya complejidad sea O(n*log(n)).

Plantear más soluciones.

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE !FALSE
typedef int Bool;

/* Algoritmo O(n^2). Analizando todos los casos. */
Bool f1(int *a, int x, int tam);

/* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. Me queda 2*n*log(n) que es O(n*log(n))*/
Bool f2(int *a, int x, int tam);
void quicksort(int *, int, int);
void pivot(int *, int, int, int *);
void swap(int *, int, int);

int main()
{
int tam, contador, x;
Bool b;

printf("Ingrese 'x': ");
scanf("%d", &x);
printf("Tamaño del array (>=2): ");
scanf("%d", &tam);
int *a = (int *) calloc (tam, sizeof(int));

for(contador=0; contador<tam; contador++)
{
printf("Ingrese el contenido de la celda %d: ", contador);
scanf("%d", &a[contador]);
}

printf("\n\n");
for(contador=0; contador<tam; contador++)
printf("%d  ", a[contador]);

/* ********************************************** */
b = f2(a, x, tam); /* solo cambiar "f1" por "f2" para cambiar de algoritmos */
if(b == TRUE)
printf("\n\nHay solucion\n");
else
printf("\n\nNo hay solucion\n");
/* ********************************************** */

free(a);
a=NULL;

system("pause");
return 0;
}

/* Algoritmo O(n^2). Analizando todos los casos. */
Bool f1(int *a, int x, int tam)
{
Bool b=FALSE;
int i, j;
for(i=0; i<tam; i++)
for(j=0; j<tam; j++)
if(a[j]+a[i] == x)
return b=TRUE; /* solución encontrada */

return b; /* no hay solución */
}

/* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. */
Bool f2(int *a, int x, int tam)
{
quicksort(a, 0, tam-1);

Bool b = FALSE;
int izq=0, med, der=tam-1, k=0;

while(izq<=der && !b && k<tam)
{
med = (izq+der)/2;

if( x<(a[k]+a[med]) )
der = med;
else if ( x>(a[k]+a[med]) )
izq = med;
else if ( x==(a[k]+a[med]) )
return b=TRUE; /* hay solución */

k++;
}

return b; /* no hay solución */
}

void quicksort(int *a, int izq, int der)
{
int piv;
if(izq<der)
{
pivot(a, izq, der, &piv);
/* { Para todo x en a: a[izq,piv] son <= a[piv] && */
/* Para todo x en a: a[piv+1,der] son > a[piv] } */
quicksort(a, izq, piv-1);
quicksort(a, piv+1, der);
}
}

void pivot(int *a, int izq, int der, int *piv)
{
int i = izq+1;
int j = der;
*piv = izq;

while(i <= j)
{
/* { *piv<i<=j+1 && (Para todo x en a: a[izq,i]<=a[*piv]) && (Para todo x en a: a[j+1,der] > a[*piv]) } */
if(a[i] <= a[*piv])
i=i+1;
else if(a[j] > a[*piv])
j=j-1;
else if(a[i] > a[*piv] && a[j] <= a[*piv])
{
swap(a, i, j);
i = i+1;
j = j+1;
}
}
/* i vale j+1, (Para todo x en a: a[izq,j] <= a[*piv]) && (Para todo x en a: a[i,der] > a[piv] */

/* dejando el pivot en una posición más central */
swap(a, *piv, j);
/* nueva posición para pivot */
*piv = j;
}

void swap(int *a, int i, int j)
{
int aux = a[i];
a[i] = a[j];
a[j] = aux;
}

Saludos

[leogtz]

La verdad no entiendo el enunciado, ¿podrias explicar con tus palabras de que trata el algoritmo?

[j retirado]

Tienes un array, ejemplo: a = [1,2,3,4,5,6,7]
Sea x = 5

Código (c) [Seleccionar] Expandir

¿Existen un a[i] y un a[j] tal que a[i]+a[j] = x?
Verdadero. En particular, a[1]+a[2] = 5.


Si quieres puedes mostrar los índices, todas las soluciones, etc. Pero es simplemente decir "si" si hay al menos una solución ó "no" si no existe solución.

Saludos.

PD: uso la etiqueta code sino me imprime una parte en cursiva...

[leogtz]

Oh, ya entiendo un poco más, en caso de lo contrario hasmelo saber, a ver si era esto:

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
int main()
{
    signed int n_elementos, numero_usuario;
    do
    {
    printf("\nNumero de elementos : ");
    setbuf(stdin, NULL);
    } while(scanf("%d", &n_elementos) != 1);
    signed int *array = (int *)malloc(n_elementos * sizeof(int));
    for(signed int i = 0; i < n_elementos; i++)
    {
        printf("array[%d] = ", i);
        scanf("%i", &array[i]);
    }
    do
    {
    printf("Numero : ");
    setbuf(stdin, NULL);
    } while(scanf("%d", &numero_usuario) != 1);
    for(signed int i = 0; i < n_elementos; i++)
    {
        for(signed int j = 0; j < n_elementos; j++)
        {
            if(array[i] + array[j] == numero_usuario)
            {
                printf("array[%d] + array[%d] = %d\n", i, j, numero_usuario);
            }
        }
    }
    return 0;
}


Salida de ejemplo:

Código [Seleccionar] Expandir


C:\>codes.exe

Numero de elementos : 10
array[0] = 10
array[1] = 20
array[2] = 30
array[3] = 40
array[4] = 50
array[5] = 60
array[6] = 70
array[7] = 80
array[8] = 90
array[9] = 100
Numero : 50
array[0] + array[3] = 50
array[1] + array[2] = 50
array[2] + array[1] = 50
array[3] + array[0] = 50

C:\>

Saludos.

[leogtz]

Lo hice a función y lo acorté:

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
void busqueda(signed int array[], signed int n_elementos, signed int numero);
int main()
{
    signed int n_elementos, numero_usuario;
    do
    {
    printf("\nNumero de elementos : ");
    setbuf(stdin, NULL);
    } while(scanf("%d", &n_elementos) != 1);
    signed int *array = (int *)malloc(n_elementos * sizeof(int));
    for(signed int i = 0; i < n_elementos; i++)
    {
        printf("array[%d] = ", i);
        scanf("%i", &array[i]);
    }
    do
    {
    printf("Numero : ");
    setbuf(stdin, NULL);
    } while(scanf("%d", &numero_usuario) != 1);
    busqueda(array, n_elementos, numero_usuario);
    return 0;
}
void busqueda(signed int array[], signed int n_elementos, signed int numero_usuario)
{
    for(signed int i = 0; i < n_elementos; i++)
        for(signed int j = 0; j < n_elementos; j++)
            if(array[i] + array[j] == numero_usuario)
                printf("array[%d] + array[%d] = %d\n", i, j, numero_usuario);
}


Salida:

Código [Seleccionar] Expandir


C:\>codes.exe

Numero de elementos : 10
array[0] = 10
array[1] = 20
array[2] = 30
array[3] = 40
array[4] = 50
array[5] = 60
array[6] = 70
array[7] = 80
array[8] = 90
array[9] = 100
Numero : 50
array[0] + array[3] = 50
array[1] + array[2] = 50
array[2] + array[1] = 50
array[3] + array[0] = 50

C:\>

[j retirado]

Exactamente, es eso. Ése es el algoritmo en el que analizas todos los casos, y en ese caso te queda O(n^2) donde n es la cantidad de numeros ingresados.

La otra forma (que a mi se me ocurrió, seguro hay otras) es ordenar el array con quicksort que tiene costo n*log(n). Luego uso búsqueda binaria que tiene costo log(n), en el peor caso se hacen n veces búsqueda binaria por lo tanto tengo n*log(n). En total tengo n*log(n)+n*log(n)=2*n*log(n) que es del orden de O(n*log(n)) pues las constantes multiplicativas son despreciables para n suficientemente grande.

Aunque en realidad cabe destacar que quicksort tiene costo n*log(n) en el caso medio (que es lo más probable que suceda). En tal caso lo anterior es correcto. Pero en el peor caso quicksort tiene costo n^2 (por ejemplo si el array ya esta ordenado, el pivote no queda muy al centro que digamos...). Entonces tendría n*log(n) por la busqueda binaria  y n^2 por quicksort, luego el algoritmo es n*log(n)+n^2 que es O(n^2). Pero esto en el peor caso, lo cual es mejor que usar brute force pues de esa forma me queda O(n^2).

Saludos.

[Eliptico]

¡¡¡Buenas!!!

Si restringes los valores del vector, a enteros no negativos, puedes hacer una ordenacion tipo cubeta (creo recordar que era de orden O(n)) y luego aplicar la busqueda binaria.

Hace mucho que no trabajo con metodos de ordenacion (de echo si alguna vez me hace falta alguno recurro al quick sort) y no recuerdo si se podia generalizar a un conjunto cualquiera (finito) de valores enteros.

Espero que te sirva.

¡¡¡Un saludo!!!

PD: A ver si refresco algo la memoria y puedo dejar el codigo por aqui. (de momento me toca ver Airbag )