[NotABigFan]

Dzisiaj dość ciekawe zadanie od Amazon:

Dana jest posortowana tablica liczb całkowitych, która została przesunięta cyklicznie o niewiadomą liczbę pozycji. Zaproponuj szybszy niż liniowy algorytm wyszukiwania elementu w tej tablicy.

Dla uproszczenia można założyć, że tablica nie zawiera duplikatów, oraz, że była uprzednio posortowana rosnąco.

Przesunięciem cyklicznym tablicy t o k pozycji w prawo nazwiemy taką tablicę t', że t'[i] == t[(i+k) mod len(t)] dla każdego indeksu i od 0 do len(t)-1.
np. [1, 2, 3, 4, 5] przesunięte o 2 pozycje w prawo to [4, 5, 1, 2, 3].

#dailycodingproblem #programowanie

[passage]

@NotABigFan: czyli wyszukiwanie w posortowanym buforze kołowym. Najprościej to będzie "podwójne" wyszukiwanie binarne. Zaraz może coś wyklepię :)

[WhirPool]

@NotABigFan: Tutaj wystarczy zmodyfikowane wyszukiwanie binarne. To zadanie jest rozwiązane w książce "Cracking the coding interview".

[croppz]

@NotABigFan: trochę zmodyfikowany binary search: strzelamy w środek (czyli index i), jeżeli i-1>i< i+1 to trafiliśmy, jeżeli i-1*i+1 to bierzemy prawą i tak aż nie ustrzelimy wartości minimalnej? O ile nic nie pomieszałem w opisie to by wychodziło log(n).*

[NotABigFan]

@passage: @WhirPool: Stanowczo 'zmodyfikowane/podwójne' wyszukiwanie binarne to nie jest satysfakcjonująca odpowiedź ( ͡° ͜ʖ ͡°).

@croppz: przeczytaj jeszcze raz zadanie, tu chodzi o wyszukiwanie dowolnego elmentu

[passage]

@NotABigFan: takie coś wymyśliłem https://pastebin.com/zEwHCZXM

trochę zmodyfikowany binary search, sprawdzam w którą stronę liczby rosną

[NotABigFan]

@passage: Pomyliłeś zadania chyba ( ͡° ͜ʖ ͡°)

[NotABigFan]

@NotABigFan: [17, 16, 15, 14, 13, 12, 11, 10, 9, 1, 2, 3, 4, 5, 6, 7, 8] nie jest cyklicznym przesunięciem posortowanej tablicy. To co próbowałeś rozwiązać to bin-search dla ciągu bitonicznego coś o wiele prostszego ( ͡° ͜ʖ ͡°) btw są ładniejsze rozwiązania dla tego problemu

[passage]

@NotABigFan: taki zakręcny jestem ʕ•ᴥ•ʔ

[ptasigryp]

@NotABigFan: moje rozwiązanie w swifcie: https://pastebin.com/QDEmfbjB