c - bubble - sorting algorithms pdf

Manera eficiente de buscar un elemento

Question

Recientemente tuve una entrevista, donde me hicieron una pregunta de " búsqueda ".
La pregunta fue:

Suponga que hay una matriz de enteros (positivos), de los cuales cada elemento es +1 o -1 comparación con sus elementos adyacentes.

Ejemplo:

array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

Ahora busca 7 y devuelve su posición.

Di esta respuesta:

Almacene los valores en una matriz temporal, ordénelos y luego aplique la búsqueda binaria.

Si se encuentra el elemento, devuelva su posición en la matriz temporal.
(Si el número aparece dos veces, devuelva su primera aparición)

Pero, no parecían estar satisfechos con esta respuesta.

¿Cuál es la respuesta correcta?

Answer 1

Aquí estoy dando la implementación en java ...

public static void main(String[] args) 
{       
    int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8};
    int pos=searchArray(arr,7);

    if(pos==-1)
        System.out.println("not found");
    else
        System.out.println("position="+pos);            
}

public static int searchArray(int[] array,int value)
{
    int i=0;
    int strtValue=0;
    int pos=-1;

    while(i<array.length)
    {
        strtValue=array[i];

        if(strtValue<value)
        {
            i+=value-strtValue;
        }
        else if (strtValue==value)
        {
            pos=i;
            break;
        }
        else
        {
            i=i+(strtValue-value);
        }       
    }

    return pos;
}

Answer 2

Aquí hay una solución de estilo de divide y vencerás. A expensas de (mucho) más contabilidad, podemos omitir más elementos; en lugar de escanear de izquierda a derecha, pruebe en el medio y salte en ambas direcciones.

#include <stdio.h>                                                               
#include <math.h>                                                                

int could_contain(int k, int left, int right, int width);                        
int find(int k, int array[], int lower, int upper);   

int main(void){                                                                  
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};                                   
    printf("7 first occurs at index %d/n",find(7,a,0,14));                       
    printf("but 9 first /"occurs/" at index %d/n",find(9,a,0,14));               
    return 0;                                                                    
}                                                                                

int could_contain(int k, int left, int right, int width){                        
  return (width >= 0) &&                                                         
         (left <= k && k <= right) ||                                            
         (right <= k && k <= left) ||                                            
         (abs(k - left) + abs(k - right) < width);                               
}                                                                                

int find(int k, int array[], int lower, int upper){                              
  //printf("%d/t%d/n", lower, upper);                                            

  if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1;  

  int mid = (upper + lower) / 2;                                                 

  if(array[mid] == k) return mid;                                                

  lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid]));
  if(lower >= 0 ) return lower;                                                    

  upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper]));
  if(upper >= 0 ) return upper;                                                  

  return -1;                                                                     

}

Answer 3

El enfoque presentado por John Coleman es lo que el entrevistador esperaba, con toda probabilidad.
Si está dispuesto a ir un poco más complicado, puede aumentar la longitud de omisión esperada:
Llame al valor objetivo k . Comience con el valor v del primer elemento en la posición p y llame a la diferencia kv dv con valor absoluto av . Para acelerar las búsquedas negativas, eche un vistazo al último elemento como el otro valor u en la posición o : si dv × du es negativo, k está presente (si cualquier ocurrencia de k es aceptable, puede reducir el rango del índice aquí de la manera la búsqueda binaria lo hace). Si av + au es mayor que la longitud de la matriz, k está ausente. (Si dv × du es cero, v u u es igual a k.)
Omitiendo la validez del índice: pruebe la posición ("siguiente") donde la secuencia podría volver a v con k en el medio: o = p + 2*av .
Si dv × du es negativo, encuentre k (recursivamente?) De p + av a o-au;
si es cero, u es igual a k en o.
Si du es igual a dv y el valor en el medio no es k, o au excede av,
o no encuentras k desde p + av hasta o-au,
dejar p=o; dv=du; av=au; p=o; dv=du; av=au; y sigue sondeando.
(Para un retroceso completo de los textos de los años 60, ver con Courier. Mi "1er 2do pensamiento" fue usar o = p + 2*av - 1 , lo que excluye du equals dv .)

Answer 4

Puede hacer una búsqueda lineal con pasos que a menudo son mayores que 1. La observación crucial es que, por ejemplo, si la array[i] == 4 y 7 aún no ha aparecido, el próximo candidato para 7 está en el índice i+3 . Use un bucle while que vaya repetidamente directamente al próximo candidato viable.

Aquí hay una implementación, ligeramente generalizada. Encuentra la primera aparición de k en la matriz (sujeto a la restricción + = 1) o -1 si no ocurre:

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

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d/n",first_occurence(7,a,15));
    printf("but 9 first /"occurs/" at index %d/n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

salida:

7 first occurs at index 11
but 9 first "occurs" at index -1

Answer 5

Tu enfoque es demasiado complicado. No necesita examinar cada elemento de la matriz. El primer valor es 4 , por lo que 7 está al menos a 7-4 elementos de distancia, y puede omitirlos.

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

int main (void)
{
    int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
    int len = sizeof array / sizeof array[0];
    int i = 0;
    int steps = 0;
    while (i < len && array[i] != 7) {
        i += abs(7 - array[i]);
        steps++;
    }

    printf("Steps %d, index %d/n", steps, i);
    return 0;
}

Salida del programa:

Steps 4, index 11

Editar: mejorado después de los comentarios de @Raphael Miedl y @Martin Zabel.

Answer 6

Una variación de la búsqueda lineal convencional podría ser un buen camino a seguir. Seleccionemos un elemento, digamos array[i] = 2 . Ahora, la array[i + 1] será 1 o 3 (impar), la array[i + 2] será (enteros positivos solamente) 2 o 4 (número par).

Al continuar así, se puede observar un patrón: la array[i + 2*n] contendrá números pares y, por lo tanto, se pueden ignorar todos estos índices.

Además, podemos ver que

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

por lo tanto, el índice i + 5 debe verificarse a continuación y un ciclo while puede usarse para determinar el siguiente índice a verificar, dependiendo del valor encontrado en el índice i + 5 .

Si bien esto tiene una complejidad O(n) (tiempo lineal en términos de complejidad asintótica), es mejor que una búsqueda lineal normal en términos prácticos, ya que no se visitan todos los índices.

Obviamente, todo esto se revertirá si la array[i] (nuestro punto de partida) era impar.

Answer 7

PASO 1

Comience con el primer elemento y verifique si es 7. Digamos que c es el índice de la posición actual. Entonces, inicialmente, c = 0 .

PASO 2

Si es 7, encontraste el índice. Es c . Si ha llegado al final de la matriz, explote.

PASO 3

Si no es así, entonces 7 debe ser al menos |array[c]-7| posiciones de distancia porque solo puede agregar una unidad por índice. Por lo tanto, Agregar |array[c]-7| a su índice actual, c, y vaya al PASO 2 nuevamente para verificar.

En el peor de los casos, cuando hay 1 y -1s alternativos, la complejidad del tiempo puede llegar a O (n), pero los casos promedio se entregarían rápidamente.