Wyszukiwanie liczby w ciągu w czasie stałym

Question

Na wejściu programu podany jest ciąg n (0 < n < 10^5) liczb z zakresu od -10^9 do 10^9, a następnie sprawdzamy, czy dana wartość istnieje w tym ciągu. Czy jest możliwe takie posegregowanie liczb w ciągu, aby można było w czasie stałym sprawdzać, czy istnieje w nim dana wartość? Oczywiście zliczanie w tablicy jest niemożliwe,bo nie zrobię tablicy 2 * 10^9 elementowej.

Comments

To jest ciąg arytmetyczny albo geometryczny?

---

Zwykły, losowy ciąg.

Answer 1

[-10^9, 10^9] to nie ilość elementów tylko zakres, czyli jak duże i jak małe będą te liczby. Ilość wyrazów ciągu, to n i będzie ona wynosić od 1 do 10^5, więc tablicę możesz zrobić bez problemu.

Jeśli najpierw będą podawane wyrazy ciągu, a dopiero później zapytanie czy dana liczba istnieje, to musisz te liczby gdzieś przechować.
Teraz tylko kwestia do jakiej struktury je włożysz, aby można było ją szybko przeszukiwać. To sedno tego zadania ;-)
Ewentualnie jakiego algorytmu przeszukującego użyjesz. (w tablicy na pewno odradzam liniowy)

PS. Czas sprawdzania zależy od ilości elementów i ich uporządkowania. Przygotuj się na przypadki, w których ciąg będzie miał 100000 elementów, a szukana wartość będzie pierwszym lub ostatnim wyrazem.