Այս թեմայի տեսողական ըմբռնման համար դիտեք այս տեսանյութը https://youtu.be/XK3uuAB3GUg
Երկուական որոնումը արագ և արդյունավետ որոնման մեթոդ է: Սա հստակ հասկանալու համար եկեք սկսենք որոնումների սկզբից: Մեզ տրվում են որոշակի տվյալներ, և մենք ցանկանում ենք դրանցում կոնկրետ տվյալներ փնտրել։ Այն, ինչ մենք անում ենք, վերցնում ենք յուրաքանչյուր տարր և ստուգում, թե արդյոք այն նույնն է, թե ոչ: Սա նշանակում է, որ եթե կա N տարր, մենք կարող ենք կատարել այս առաջադրանքը O(N) ժամանակի բարդության մեջ:
Թվում է, թե մինչև այս պահը ամեն ինչ լավ է, բայց ասենք, որ ես ունեմ [1,2,5,8,10,23,25,…..] նման զանգված, յուրաքանչյուր տարր ավելի մեծ է, քան իր նախորդ տարրը: Եթե մենք որոնենք այս զանգվածի որևէ տարր նախորդ մեթոդից, ապա այս հատկության օգտագործումը, այսինքն՝ զանգվածը դասավորված է (աճող հերթականությամբ): Երկուական որոնումն օգտագործվում է տվյալների տվյալ հատկությունների օգտագործմամբ որոնումն ավելի լավ իրականացնելու համար:
KEY=Տվյալների մեջ փնտրվող արժեք:
Ինչպես ենք մենք կատարում Երկուական որոնում:-օգտագործելով զանգվածը [1,2,5,8,10,23,25,…..], տրված է զանգվածը աճող կարգով, ինչը նշանակում է, եթե KEY-ը X-րդ տարրից մեծ, քան KEY-ը, ավելի մեծ է, քան X-րդ տարրից առաջ բոլոր տարրը: օգտագործելով այս հատկությունը, կատարվում են հետևյալ քայլերը.
i) Left=0, right=data.size() -1;
ii) Եթե ձախ›աջ՝ ՉԱՓԱԽՎԱԾ:
iii) Ստուգեք տվյալների միջին տարրը:
iv) Եթե միջին տարրը հավասար է KEY-ին, ՀԱՋՈՂՈՒԹՅՈՒՆ: STOP
v) Այլ: -
ա. Եթե KEY-ը միջին տարրից մեծ է, data=data[left:middle-1], right=middle-1:
բ. Այլ տվյալներ=տվյալներ[միջին+1:աջ], ձախ=միջին+1
գ. Կրկնել քայլը (i):
- Քայլ (i)-ում կապվում է որոնման շրջանը, այսինքն՝ տվյալների առաջին ինդեքսը 0 է, իսկ տվյալների վերջին ցուցանիշը՝ data.size()-1;
- Քայլ (ii) մեկնարկային ինդեքսն ավելի մեծ է, քան ավարտի ինդեքսը հնարավոր չէ, ինչը նշանակում է, որ KEY-ը տվյալների մեջ չէ:
- Քայլում (iii)՝ KEY-ի համեմատությունը տվյալների միջին տարրի հետ (վերջին որոնման շրջան):
- Քայլ (iv), եթե որոնման շրջանի միջին տարրը հավասար է KEY-ին, դադարեցրեք որոնումը, քանի որ գտնվել է տարրը:
- Քայլ (v)-ում կա երկու հնարավորություն կամ KEY-ն ավելի մեծ է, քան միջին տարրը, կամ KEY-ը փոքր է, քան միջին տարրը: Եթե KEY-ը միջին տարրից փոքր է, դա նշանակում է, որ անիմաստ է որոնել KEY-ը միջին տարրից հետո տարածաշրջանում (կատարվում է աջ ինդեքսը փոխելով), այնպես որ մենք թարմացնում ենք տվյալները միայն միջին տարրից առաջ և վերջավոր (աջ) տվյալների ինդեքսով: դառնում է միջին-1 ցուցանիշ; Միջին արժեքից մեծ KEY-ի համար հակառակը:
Ժամանակի բարդություն.- երկուական որոնումն աշխատում է O(LOG₂N)-ում` առանց որևէ լրացուցիչ տարածք օգտագործելու: Նայելով ժամանակի բարդությանը, այն դառնում է շատ արդյունավետ մեթոդ՝ համեմատած մեր նախորդ մեթոդի հետ:
Երկուական որոնման կիրառումներ.-
- Հաճախակի որոնումներ կատարելու համար:
- Հաշվել, թե քանի անգամ է տարրը հայտնվել տեսակավորված զանգվածում, (քննարկվող մեթոդի փոքր փոփոխություն)
- Ցանկացած թվի քառակուսի արմատ գտնելը:
- Գտնել զանգվածի առավելագույն արժեքը, որը սկզբում մեծանում է, ապա նվազում:
- որոնում KEY զանգվածում, որը տեսակավորումից հետո պտտվում է n անգամ: և այլն:
Սրանք երկուական որոնման որոշ կիրառումներ են:
Երկուական որոնման սահմանափակում.-
- Երկուական որոնումն աշխատում է միայն նախապես գրանցված տվյալների կամ ֆիքսված տվյալների վրա:
- Զանգվածը պետք է տեսակավորվի նախքան երկուական որոնումը կիրառելը:
- Այն չի աշխատում իրական կյանքի տվյալների վրա, ինչպիսիք են.
Երկուական որոնման այս սահմանափակումները կարող են հեռացվել առանց ալգորիթմի արդյունավետության խախտման, որը մենք կներկայացնենք հաջորդ բլոգում:
Այս անգամ հետևեք՝ յուրաքանչյուր բլոգում թարմացնելու համար:
Բարի օր և ուրախ ծրագրավորում: