"kahendotsing" - 1 õppematerjal

Algoritmi ajaline keerukus

int main() { time_t algusaeg, lopuaeg; double tooaeg; algusaeg=clock(); // algoritm lopuaeg=clock(); tooaeg=(double)((lopuaeg - algusaeg) / CLK_TCK); cout <<"tooaeg oli: "<Kahendotsing Probleemi püstitus: Eeeldatakse et massiiv on järjestatud (kasvavalt). Otsime massiivist etteantud arvuga võrdset elementi. Etteantud elementi võrdleme massiivi keskmise elemendiga, kui etteantud element on keskmisest väiksem võrdne siis jätkame otsinguid massiivi esimeses pooles vastasel korral teises pooles. Võrdleme etteantud elementi järelejäänud massiviosa keskmise elemendiga jne. Otsingu lõpu tunnusena võime kasutada tingimust et alammassiivi suurim element on suurem