Učinkovito iskanje intervalov [Psevdokoda]

Imam številsko os in na njej točke. Nekatere so bolj skupaj in nekatere narazen. Kako bi učinkovito poiskal intervale množice točk.

Primer:
Iz tega:

__+__+___+____________++____+__+_+____________+_____+

bi rad dobil nekaj takšnega:

__+______+____________+__________+____________+_____+

Torej za interval množice točk najdem prvo točko in drugo zadnjo točko. Tako da dobim par[x,y].

Problem je v tem dolžina intervalov ni točno določena, samo vem da so gruče točk na osi in te so kratki intervali, potem je dolgi interval in spet kratki kjer je gruča.

Hvala za pomoč.

Intervali so; kratek-dolg-kratek-dolg...

Išče se kratke intervale kjer je množica točk, potem sledi dolg interval kjer ni nobene točke. Nato se ponovi. Išče se samo na 1-D številski osi.

Moja nedelujoča rešitev je takšna:

x = 0;
y = 0;

while (i < interval)
   while (j = i + 1 < interval)
      if (interval(j) - interval(i) < konstanta)
             j++;
   x = interval(i);
   y = interval(j);

Tako se najde en interval, [x,y] želel bi imeti množico kratkih intervalov znotraj katerih bi bile točke.

Saj zato me zanima, če ima kdo izkušnje z algoritmi kjer se išče gruče točk, ker intervali niso določeni, nekje je kratek interval dolg 20, nekje 30. Dolgi so pa okoli 400 do 500, vendar ne nujno.

Vhodni podatek, je dejansko vektor, ki vsebuje števila:
Primer:
[23,39,42,300,312,342,500...]

To so točke na 1D x osi. To je vse. Izračunam razdalje med posameznimi števili, vidim da je nekje 20-30 razlike nekje več kot 400. Vendar moramo biti pazljivi saj je nekje točk več na intervalu nekje pa samo 2.

Ni nujno da za vse dobro dela, vendar mora za vsaj večino.

Metoda bisekcije? Kako si točno mislil? Metoda se uporablja za iskanje elementov v urejeni tabeli.

Sorry ker ne razumem, vendar me že glava boli od programiranja.

Hvala za odgovor.

Če se greš takšno "mehko" metodo, kjer je njen rezultat odvisen od nekih magičnih parametrov, je dobro zraven vedet sploh kakšen namen želiš dosečt.
Se greš kompresijo podatkov? Mora bit lossless? Se greš kej tretjega in si lahko "mal" nenatančen?

Ce dopuscas intervale dolzine 0 (torej iz ene tocke) potem je povsem nemogoce brez nekih dodatnih parametrov, ki jih moras izbrat.
Na splosno moras zahtevat postavljat nek minimum razdalj med tockami al pa recimo stevilo grup, ki jih hoces dosezt. Lahko imas meta hevristiko ko variras stevilo grup in racunas neko metriko, na podlagi katere izberes. Brez tega pa bolj tezko, ker ce zdruzujes une tocke k so blizu in imas poljubno stevilo grup, potem ponavadi algoritem kot najboljso resitev najde kopico grup iz malo tock, ki so si res blizu. Kar je pa ponavadi dalec od tega kar bi clovek izbral.

Glede na opis problema, bi rekel da imaš opravka s clusteringom. Zakaj torej ne bi uporabil kar za to namenskih algoritmov?
Pa če te tvoje vektorje točk dodajaš inkrementalno, lahko uporabiš kak lazy learning algoritem ala kNN: K-nearest neighbors algorithm @ Wikipedia