Wyszukanie wartości równej indeksowi w tablicy

0

Cześć, miałem do rozwiązania pewne zadanie, mianowicie wymyślić algorytm, który w uporządkowanej tablicy liczb całkowitych(również ujemnych) znajdzie wartość równą swojemu indeksowi np. tab[5]=5. Wiadomo że mógłbym przeszukać całą tablicę od początku do końca, ale w zadaniu było napisane "efektywny algorytm", więc podejrzewam że chodzi o coś o mniejszej złożoności obliczeniowej.

Trochę się nad tym zastanawiałem aż w końcu zobaczyłem w treści słowo klucz "różne" w zdaniu "posortowana tablica n różnych liczb całkowitych". W tym momencie problem znikł - wiadomo wyszukiwanie binarne i jesteśmy w domu.

Jednak co gdyby wartości w tablicy mogły się powtarzać? Myślałem o trochę innej idei "wyszukiwania binarnego" zrealizowanej w sposób rekurencyjny, która dzieliłaby tablice na pół, później rekurencją połówki na ćwiartki itd i zamiast wskazywać połówkę w której prawdopodobnie znajduje się element odrzucała by tą połówkę w której takiego elementu na pewno nie ma. Na przykład gdyby element środkowy był ujemny wtedy wiadomo że wszystko co na lewo odrzucamy bo indeksy zaczynają się od 0. Przechodzimy do kolejnej połówki dzielimy ją i okazuje się że nowy środek ma wartość większą niż rozmiar tablicy więc znowu odrzucamy. Wiem że przykład jest bardzo optymistyczny bo po 2 krokach odrzuciliśmy 75% tablicy, ale chciałem przedstawić ideę.

Generalnie już wiem, że coś takiego raczej nie wypali bo w przypadku pesymistycznym i tak otrzymam złożoność n i jeszcze do tego rekurencja więc wgl po zawodach, natomiast jestem ciekaw czy wgl istnieje jakieś lepsze rozwiązanie problemu niż przeszukiwanie całej tablicy i jeśli tak to jak ono wygląda?

Temat pewnie nie najciekawszy, ale będę wdzięczny również za potwierdzenie że nie ma lepszego sposobu jeśli faktycznie tak jest :)

1

Skoro tablica uporządkowana, to jeśli tab[i] = x, oraz x > i, to skacz od razu do tab[x], bo nigdzie wcześniej trafienia nie znajdziesz.

2

Jest na to jakiś tam algorytm, tak z głowy rzucam:

  • wyszukiwanie binarne porównujące wartość z indeksem (zamiast wartość z elementem)

Jak radzić sobie z duplikatami: (k elementów == indeksowi tablicy)
https://stackoverflow.com/a/13197618

1 użytkowników online, w tym zalogowanych: 0, gości: 1