Mam pytanie, czy da się jakoś podzielić tablicę jednowymiarową (w czasie logn) na 2 części, aby elementem dzielącym nie był żaden element tablicy, a jakaś dowolna liczba? Jeśli tak, to jak to zaimplementować?
0
0
Zakładając że element dzielący oznacza że elementy większe lub równe do jednej tablicy a mniejsze do drugiej, to kluczową kwestią jest czy ta tablica jest posortowana. Jak nie to bez przejrzenia całej się nie obejdzie. Jak tak to można myśleć jak najszybciej znaleźć element graniczny/najbliższy mu ( np sprawdzić środkowy a potem podzielić tablicę na pół, wróć na początek algorytmu)
0
Jeżeli tablica nie jest posortowana to się nie da w czasie log(n).
Jeżeli jest posortowana to metoda połowienia (bisekcji) daje czas log(n)