Skuteczny sposób wyszukiwania elementu

Niedawno miałem wywiad, w którym zadali mi „ szukające ” pytanie.
Pytanie brzmiało:

Zakłada się, że jest tablicą (pozytywnych) całkowitymi, przy czym każdy z elementów jest albo +1czy -1w stosunku do sąsiednich elementów.

Przykład:

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

Teraz wyszukaj 7i zwróć jego pozycję.

Odpowiedziałem:

Przechowuj wartości w tymczasowej tablicy, posortuj je, a następnie zastosuj wyszukiwanie binarne.

Jeśli element zostanie znaleziony, zwróć jego pozycję w tymczasowej tablicy.
(Jeśli liczba występuje dwukrotnie, zwróć jej pierwsze wystąpienie)

Ale wydawało się, że ta odpowiedź nie zadowoliła ich.

Jaka jest właściwa odpowiedź?

Możesz przeprowadzić wyszukiwanie liniowe z krokami, które są często większe niż 1. Kluczową obserwacją jest to, że jeśli np. array[i] == 4I 7 jeszcze się nie pojawiło, to następny kandydat na 7 jest pod indeksem i+3. Użyj pętli while, która wielokrotnie przechodzi bezpośrednio do następnego realnego kandydata.

Oto implementacja, nieco uogólniona. Znajduje pierwsze wystąpienie kw tablicy (z zastrzeżeniem ograniczenia + = 1) lub -1jeśli nie występuje:

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

wynik:

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

Twoje podejście jest zbyt skomplikowane. Nie musisz sprawdzać każdego elementu tablicy. Pierwsza wartość jest 4, tak 7jest przynajmniej 7-4 elementy z dala, i można pominąć tych.

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

Wyjście programu:

Steps 4, index 11

Edycja: poprawiona po komentarzach @Raphael Miedl i @Martin Zabel.

Odmiana konwencjonalnego wyszukiwania liniowego może być dobrym rozwiązaniem. Wybierzmy element, powiedzmy array[i] = 2. Teraz array[i + 1]będzie 1 lub 3 (nieparzyste), array[i + 2]będzie (tylko dodatnie liczby całkowite) 2 lub 4 (liczba parzysta).

Kontynuując w ten sposób, można zaobserwować wzór - array[i + 2*n]będzie zawierał liczby parzyste, więc wszystkie te wskaźniki można zignorować.

My też to widzimy

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

tak więc indeks i + 5powinien być sprawdzony jako następny, a pętla while może być użyta do określenia następnego indeksu do sprawdzenia, w zależności od wartości znalezionej w index i + 5.

Chociaż ma to złożoność O(n)(czas liniowy pod względem złożoności asymptotycznej), w praktyce jest lepsze niż zwykłe wyszukiwanie liniowe, ponieważ nie wszystkie indeksy są odwiedzane.

Oczywiście wszystko to zostanie odwrócone, jeśli array[i](nasz punkt wyjścia) był dziwny.

Podejście przedstawione przez Johna Colemana jest tym, na co najprawdopodobniej liczył ankieter.
Jeśli chcesz trochę bardziej skomplikować, możesz zwiększyć oczekiwaną długość przeskoku:
wywołaj wartość docelową k . Zacznij od wartości v pierwszego elementu na pozycji p i wywołaj różnicę kv dv z wartością bezwzględną av . Aby przyspieszyć negatywne wyszukiwania, zerknij na ostatni element jako drugą wartość u na pozycji o: jeśli dv × du jest ujemne, występuje k (jeśli jakiekolwiek wystąpienie k jest dopuszczalne, możesz zawęzić zakres indeksu tutaj, tak jak robi to wyszukiwanie binarne). Jeśli av + au jest większe niż długość tablicy, k jest nieobecne. (Jeśli dv x du wynosi zero, V lub U równa k.)
Pomijając słuszność indeksu: Sonda przycisk ( „Next”) pozycja, w której sekwencja może powrócić do v k w środku: o = p + 2*av.
Jeśli dv × du jest ujemne, znajdź k (rekurencyjnie?) Od p + av do o-au;
jeśli jest równe zero, u równa się k przy o.
Jeśli du jest równe dv, a wartość w środku nie jest k, lub au przekracza av,
lub nie możesz znaleźć k od p + av do o-au,
pozwól p=o; dv=du; av=au;i kontynuuj sondowanie.
(Aby uzyskać pełny powrót do tekstów z lat 60-tych, obejrzyj je w Courier. Moją „pierwszą drugą myślą” było użycieo = p + 2*av - 1, co wyklucza du equals dv .)

KROK 1

Zacznij od pierwszego elementu i sprawdź, czy jest 7. Powiedzmy, że cjest to indeks aktualnej pozycji. Tak więc początkowo c = 0.

KROK 2

Jeśli jest 7, znalazłeś indeks. To jest c. Jeśli osiągnąłeś koniec tablicy, wyrwij się.

KROK 3

Jeśli tak nie jest, 7 musi znajdować się co najmniej na |array[c]-7|pozycjach dalej, ponieważ możesz dodać tylko jednostkę na indeks. Dlatego dodaj |array[c]-7|do bieżącego indeksu c i ponownie przejdź do KROKU 2, aby sprawdzić.

W najgorszym przypadku, gdy występują naprzemiennie 1 i -1, złożoność czasowa może osiągnąć O (n), ale przeciętne przypadki byłyby dostarczane szybko.

Tutaj podaję implementację w 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;
}

Oto rozwiązanie w stylu „dziel i rządź”. Kosztem (dużo) większej księgowości możemy pominąć więcej elementów; zamiast skanować od lewej do prawej, testuj na środku i pomijaj w obu kierunkach.

#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);

Chciał dołączyć rekursywne rozwiązanie problemu. Cieszyć się