Երկուական որոնում ընդդեմ գծային որոնման
Գծային որոնումը, որը նաև հայտնի է որպես հաջորդական որոնում, որոնման ամենապարզ ալգորիթմն է: Այն որոնում է նշված արժեք ցանկում՝ ստուգելով ցանկի յուրաքանչյուր տարր: Երկուական որոնումը նաև մեթոդ է, որն օգտագործվում է տեսակավորված ցուցակում նշված արժեքը գտնելու համար: Երկուական որոնման մեթոդը կրկնակի նվազեցնում է ստուգված տարրերի քանակը (յուրաքանչյուր կրկնության դեպքում)՝ նվազեցնելով տվյալ կետը ցուցակում գտնելու ժամանակը։
Ի՞նչ է գծային որոնումը:
Գծային որոնումը որոնման ամենապարզ մեթոդն է, որը հաջորդաբար ստուգում է ցանկի յուրաքանչյուր տարր, մինչև այն գտնի նշված տարրը:Գծային որոնման մեթոդի մուտքագրումը հաջորդականություն է (օրինակ՝ զանգված, հավաքածու կամ տող) և այն տարրը, որը պետք է որոնվի: Արդյունքը ճշմարիտ է, եթե նշված տարրը տրված հաջորդականության մեջ է, կամ կեղծ, եթե այն հաջորդականության մեջ չէ: Քանի որ այս մեթոդը ստուգում է ցանկի բոլոր տարրերը, մինչև նշված տարրը գտնվի, վատագույն դեպքում այն կանցնի ցանկի բոլոր տարրերը՝ նախքան անհրաժեշտ տարրը գտնելը: Գծային որոնման բարդությունը o(n) է: Հետևաբար, այն համարվում է շատ դանդաղ՝ մեծ ցուցակներում տարրեր որոնելիս օգտագործելու համար: Բայց սա շատ պարզ է և հեշտ իրագործելի:
Ի՞նչ է Երկուական որոնումը:
Երկուական որոնումը նաև մեթոդ է, որն օգտագործվում է տեսակավորված ցանկում նշված տարրը գտնելու համար: Այս մեթոդը սկսվում է որոնված տարրը համեմատելով ցանկի մեջտեղում գտնվող տարրերի հետ: Եթե համեմատությունը պարզում է, որ երկու տարրերը հավասար են, մեթոդը դադարում է և վերադարձնում տարրի դիրքը: Եթե որոնված տարրը ավելի մեծ է, քան միջին տարրը, այն նորից սկսում է մեթոդը՝ օգտագործելով տեսակավորված ցանկի միայն ստորին կեսը:Եթե որոնված տարրը միջին տարրից փոքր է, այն նորից սկսում է մեթոդը՝ օգտագործելով միայն տեսակավորված ցանկի վերին կեսը։ Եթե որոնված տարրը ցուցակում չէ, մեթոդը կվերադարձնի եզակի արժեք, որը ցույց է տալիս դա: Հետևաբար երկուական որոնման մեթոդը կիսով չափ կրճատում է համեմատվող տարրերի քանակը (յուրաքանչյուր կրկնության մեջ)՝ կախված համեմատության արդյունքից: Հետևաբար, երկուական որոնումն իրականացվում է լոգարիթմական ժամանակում, ինչը հանգեցնում է o(log n) գործի միջին կատարման:
Ո՞րն է տարբերությունը Երկուական որոնման և գծային որոնման միջև:
Թեև և՛ գծային որոնումը, և՛ երկուական որոնումը որոնման մեթոդներ են, նրանք ունեն մի քանի տարբերություն: Մինչ երկուական որոնումը գործում է տեսակավորված ցուցակների վրա, գծային որոնումը կարող է գործել նաև չտեսակավորված ցուցակների վրա: Ցանկի տեսակավորումը սովորաբար ունի n log n գործի միջին բարդություն: գծային որոնումը պարզ և պարզ է իրականացնել, քան երկուական որոնումը: Սակայն գծային որոնումը չափազանց դանդաղ է մեծ ցուցակներով օգտագործելու համար՝ իր o(n) գործի միջին կատարողականության պատճառով:Մյուս կողմից, երկուական որոնումը համարվում է ավելի արդյունավետ մեթոդ, որը կարող է օգտագործվել մեծ ցուցակներով: Բայց երկուական որոնման իրականացումը կարող է բավականին բարդ լինել, և ուսումնասիրությունը ցույց է տվել, որ երկուական որոնման ճշգրիտ կոդը կարելի է գտնել քսան գրքերից միայն հինգում:
