Այս թեմայի տեսողական ըմբռնման համար դիտեք այս տեսանյութը 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 անգամ: և այլն:

Սրանք երկուական որոնման որոշ կիրառումներ են:

Երկուական որոնման սահմանափակում.-

  • Երկուական որոնումն աշխատում է միայն նախապես գրանցված տվյալների կամ ֆիքսված տվյալների վրա:
  • Զանգվածը պետք է տեսակավորվի նախքան երկուական որոնումը կիրառելը:
  • Այն չի աշխատում իրական կյանքի տվյալների վրա, ինչպիսիք են.

Երկուական որոնման այս սահմանափակումները կարող են հեռացվել առանց ալգորիթմի արդյունավետության խախտման, որը մենք կներկայացնենք հաջորդ բլոգում:

Այս անգամ հետևեք՝ յուրաքանչյուր բլոգում թարմացնելու համար:

Բարի օր և ուրախ ծրագրավորում: