Sortowanie binarne/interpolarne

dzień dobry! Mam do napisania program który dostaje uporządkowany rosnąco ciąg liczb i przedział <a,b> dla tego przedziału ma wyznaczyć liczbę cyfr która się w nim znajduje. Problem polega na tym że nie przejdzie coś takiego że sobie wyszukam binarnie indeksy a i b a później i _a - i_b +1 i mam wszystko co trzeba. Trzeba to zrobić szybciej w sensie wyznaczyć binarnie największy element z podanego przedziału i mając jego indeks wyznaczyc ten drugi. Intuicyjnie widać że będzie to coś na zasadzie wyznaczania interpolarnego, no ale nie za bardzo to jednak widzę. Prosiłbym o jakąś wskazówkę. Pozdrawiam

Szybciej niż O(2*log(n))? Mam wątpliwości czy się da, a przynajmniej nie w każdym przypadku. To jest co potrzebne do jakiegoś SPOJa? Bo mam wrażenie że ten fragment algorytmu raczej nie "spowalnia" ci programu.

Złożoność w tym wypadku jest 2nlog(n) z racji dużej ilości zestawów, a powinno być coś na zasadzie n*log(n) +k gdzie k<n. No nie wiem program napiszę dopiero dziś. Tak to jest coś na zasadzie spoja tylko że wiem jaka złożoność przechodzi przez system/serwer.

A czy liczby będące granicami przedziału są zawsze zawarte w wejściowym ciągu? Bo jeśli tak to można zrobić tak:
robimy sobie hashmapę gdzie kluczem jest liczba, a wartością jej jest numer w ciągu wejściowym.
W ten sposób odszukanie indeksów granic przedziału mamy średnio w 2O(1)
W efekcie zamiast O(n)+2O(log(n)) mamy O(n)+2*(1)
(O(n) to jest czas potrzebny na wczytanie N liczb z wejścia)

Trollek napisał(a):

Złożoność w tym wypadku jest 2nlog(n)
Wyszukiwanie binarne to O(log N), a nie O(N*log(N))

Zamiast wyszukiwać dwukrotnie w całym zbiorze możesz najpierw wyszukać binarnie dowolny element z przedziału jednocześnie zawężając zbiór wejściowy:

while poczatek < koniec
    srodek = (poczatek + koniec) / 2
    if zbior[srodek] < minimum
        poczatek = srodek
    else if zbior[srodek] > maksimum
        koniec = srodek
    else
        break

(algorytm obrazowy, wymaga dopracowania, indeksy +1 lub -1 gdzieniegdzie)

I teraz szukany element najmniejszy znajduje się między poczatek a srodek a największy między srodek a koniec, trzeba je wyszukać binarnie. W ten sposób zamiast 2*log(n) operacji robimy log(n) prawie identycznych operacji.

Shalom napisał(a):

robimy sobie hashmapę gdzie kluczem jest liczba, a wartością jej jest numer w ciągu wejściowym

To wymaga N operacji wstawiania do hashmapy! Raczej niedobry pomysł.

O(log N) jest całkiem zadowalające. Przede wszystkim trzeba minimalizować to co ma się wykonać w O(N). Zapewne głównym czynnikiem będzie szybkość z jaką wczytamy liczby z wejścia...

OK, z tego co też sam wydedukowałem szybciej nie będzie trza szukać obu końców ale skorzystam z rady adf88 i biorę się za pisanie.
Jeszcze jedna uwaga a propos pomysłu użytkownika Shalom niestety ciąg wejściowy może mieć postać np. 3 4 4 4 6 7 8 9 9 50 99