Cawte,
na hladanie v utriedenom zozname pouzivame binary search s casovou
zlozitostou log(n). Ale ak mam zoznam s utriedenimi prvkami, pricom
pre i-ty prvok plati, ze rozdiel medzi prvkami i a i-1 je mensi ako
medzi i-1 a i-2, da sa to nejak rychlejsie ako log(n)?
Vyhladavanie v utriedenom poli
Pre pridávanie komentárov sa musíte prihlásiť.
Ak tych cisel hladame viac, vieme si spocitat sucet medzier. No ak sa tie medzery medzi cislami zmensuju, tak vieme, ze predposledna medzera je minimalne rovna poslednej a taktiez potom vieme aky je sucet medzier od prvej po predposlednu (ak si ich na zaciatku scitame). Neda sa nejak takto skakat od poslednej hodnoty pola az k hladanej (ak existuje) na menej nez log(n) krokov (napr log(log(n)) alebo log*(n))?
ak hladas viac cisel, mozno by stalo za uvahu ich zotriedit a vyhladavat tiez delenim intervalov...myslim, ze mas cisla 1, 5, 8, 12, 24 a ty chces vyhladat 8. A ak sa dostanes do situacie, ze vsetky cisla su vacsie ako 8, tak 1 a 5 uz nemusis hladat.