Manera eficiente de buscar un elemento

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

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

Ejemplo:

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

Ahora busque 7y devuelva 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, devuelve 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?

Puede hacer una búsqueda lineal con pasos que a menudo son mayores que 1. La observación crucial es que si eg array[i] == 4y 7 aún no han aparecido, el siguiente candidato para 7 está en index i+3. Utilice un ciclo while que repetidamente va directamente al siguiente candidato viable.

Aquí hay una implementación, ligeramente generalizada. Encuentra la primera aparición de ken la matriz (sujeto a la restricción + = 1) o -1si 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

Tu enfoque es demasiado complicado. No es necesario examinar todos los elementos de la matriz. El primer valor es 4, por lo que se 7encuentran al menos 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.

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

Al continuar así, se puede observar un patrón: array[i + 2*n]mantendrá números pares, por lo que todos estos índices pueden ignorarse.

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 se i + 5debe verificar a continuación y se puede usar un ciclo while para determinar el siguiente índice a verificar, dependiendo del valor encontrado en el índice i + 5.

Si bien esto tiene 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 array[i](nuestro punto de partida) fue extraño.

El enfoque presentado por John Coleman es lo que esperaba el entrevistador, con toda probabilidad.
Si está dispuesto a hacerlo un poco más complicado, puede aumentar la longitud de salto esperada:
Llame al valor objetivo k . Comience con el valor v del primer elemento en la posición py llame a la diferencia kv dv con el 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í como lo hace la búsqueda binaria). Si av + au es mayor que la longitud de la matriz, k está ausente. (Si dv du × es cero, V o U es igual a k.)
La omisión de validez índice: Sonda de la ( "siguiente") posición en la que 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 puede encontrar k de p + av a o-au,
deje p=o; dv=du; av=au;y siga probando.
(Para ver un flashback completo a los textos de los años 60, ver con Courier. Mi "primer segundo pensamiento" fue usaro = p + 2*av - 1, lo que excluye du es igual a dv .)

PASO 1

Comience con el primer elemento y verifique si es 7. Digamos que ces el índice de la posición actual. Así, en un principio, c = 0.

PASO 2

Si es 7, encontró el índice. Es c. Si ha llegado al final de la matriz, rompa.

PASO 3

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

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

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;
}

Aquí hay una solución estilo divide y vencerás. A expensas de (mucha) 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;                                                                     

}

const findMeAnElementsFunkyArray = (arr, ele, i) => {
  const elementAtCurrentIndex = arr[i];

  const differenceBetweenEleAndEleAtIndex = Math.abs(
    ele - elementAtCurrentIndex
  );

  const hop = i + differenceBetweenEleAndEleAtIndex;

  if (i >= arr.length) {
    return;
  }
  if (arr[i] === ele) {
    return i;
  }

  const result = findMeAnElementsFunkyArray(arr, ele, hop);

  return result;
};

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

const answer = findMeAnElementsFunkyArray(array, 7, 0);

console.log(answer);

Quería incluir una solución recursiva al problema. Disfrutar