Szukam najszybszego sposobu, aby zdecydować, czy punkt na linii znajduje się w podzbiorze tej linii. Otrzymuję punkt całkowity, a także „listę”:

Punkty reprezentowane przez liczbę całkowitą (3, 10, 1000 itd.)Interwały, które reprezentuję za pomocą 2 liczb całkowitych (2:10 to wszystkie liczby całkowite od 2 do 10, 50:60 itd.)

W tym przykładzie, jeśli wartość mojego punktu wynosi 5, to zwracam true, ponieważ jest on zawarty w interwale, taki sam dla 55. Jeśli mój punkt jest równy 1000, zwracam również true, ponieważ pasuje do listy punktów.

Szukam szybkiego sposobu (szybszego niż liniowy), aby sprawdzić ten warunek, BEZ konieczności ustanawiania tylu liczb całkowitych, ile jest możliwych punktów (tj. Dla interwału 1: 1000 nie chcę instancować 1000 liczb całkowitych). Czy można to zrobić w czasie logarytmicznym?

Dzięki

edit: możesz wziąć pod uwagę, że każdy czas potrzebny do wstępnego przetworzenia listy danych jest równy 0, ponieważ po przetworzeniu początkowych interwałów muszę zastosować ten test do 10k punktów