Երկուական (բինար) որոնում

Երկուական որոնումը (Binary search) արդյունավետ ալգորիթմ է տեսակավորված տարրերի ցանկից որևէ տարր գտնելու համար։ Այն աշխատում է ցանկի որոշ մասը շարունակաբար կիսելով այնքան ժամանակ, մինչև կգտնվեն տվյալ տարրի հնարավոր ուղղությունները։ Մենք երկուական որոնում օգտագործեցինք ներածական բաժնում՝ թիվը գուշակելու խաղում։

Զանգվածում (array) տարրը գտնելու համար հաճախ կիրառում են երկուական որոնման ալգորիթմը։ Օրինակ՝ Թայքո-2 աստղերի տեղեկագիրքը տիեզերքում 2,539,913 պայծառ աստղերի մասին տեղեկություն է պարունակում։ Պատկերացրու՝ ուզում ես տեղեկագրքում որևէ աստղի մասին տեղեկություն փնտրել՝ հիմք ընդունելով աստղի անունը։ Եթե ծրագիրը հերթով դիտարկեր ամեն մի աստղը, այսինքն՝ օգտագործեր գծային որոնման ալգորիթմը, համակարգիչը վատագույն դեպքում կդիտարկեր 2,539,913 աստղ՝ մինչև քո ուզած աստղը գտնելը։ Եթե տեղեկագիրքում աստղերի անվանումները դասավորված լինեն այբբենական հերթականությամբ՝ ըստ անվանումների առաջին տառերի, երկուական որոնմամբ առավելագույնը 22 քայլով կգտնես քո ուզած աստղը։

Հաջորդ մի քանի հոդվածներում կխոսենք ալգորիթմի մասին՝ ինչպես օգտագործել ալգորիթմը JavaScript-ում և ինչպես արդյունավետ կերպով վերլուծել այն։

Երբ մարդուն ներկայացնում ես ալգորիթմը, թերի նկարագրությունը հաճախ միանգամայն բավարար է։ Երբ տորթ ես պատրաստում, բաղադրատոմսը ենթադրում է, որ գիտես, թե ինչպես բացես սառնարանը, վերցնես հավկիթն ու ջարդես այն։ Մարդիկ ենթագիտակցորեն գիտեն՝ ինչպես լրացնել բացերը, իսկ համակարգչային ծրագրերը չեն կարողանում։ Այդ իսկ պատճառով մենք պետք է ամբողջությամբ նկարագրենք համակարգչային ալգորիթմները:

Ծրագրավորման լեզվի մեջ ալգորիթմ օգտագործելու համար պետք է հասկանաս ալգորիթմի բոլոր առանձնահատկությունները։ Ինչե՞ր են մուտքագրվում խնդրում։ Որո՞նք են արդյունքները։ Ի՞նչ փոփոխականներ պետք է ստեղծվեն, և ի՞նչ սկզբնական արժեքներ դրանք պետք է ունենան։ Ի՞նչ միջանկյալ քայլեր պետք է կատարես՝ մնացած արժեքները հաշվելու համար, և ինչպե՞ս հաշվես ընդհանուր արդյունքը։ Այս քայլերն ունե՞ն արդյոք կրկնվող հրահանգներ, որոնք կարելի է գրել ավելի պարզեցված տեսքով, օրինակ՝ ցիկլի (loop) տեսքով։

Արի փորձենք հնարավորինս ճիշտ նկարագրել երկուական որոնումը։ Երկուական որոնման նպատակն է հետևել տրամաբանական կռահումների միջակայքին: Ենթադրենք՝ 1-ից 100 միջակայքում թիվ եմ մտապահել, ինչպես «Գուշակիր թիվը» խաղում։ Եթե, օրինակ՝ գուշակում ես՝ 25, և ես քեզ ասում եմ, որ իմ թիվը մեծ է դրանից, իսկ հետո գուշակում ես՝ 81, այնուհետև ասում եմ, որ իմ մտապահած թիվը փոքր է 81-ից, ուրեմն միայն 26-ից 80-ն ընկած միջակայքի թվերն են տրամաբանական կռահումները։ Բերված նկարում թվային միջակայքի կարմիր հատվածը ցույց է տալիս տրամաբանական կռահումները, իսկ սև հատվածը՝ բացառված տարբերակները․

Ամեն անգամ մտապահված թիվը գուշակելիս տրամաբանական գուշակումների բազմությունը բաժանվում է երկու հավասար մասերի: Եթե քո գուշակումը սխալ է, և եթե ասեմ, որ քո թիվը շատ մեծ կամ փոքր է, այդպես կարող ես տրամաբանական գուշակումների ուղիղ կեսը հանել։ Մեր օրինակում եթե տրամաբանական գուշակումների միջակայքը 26-ից 80-ն է, քո ենթադրած թիվը պետք է լինի դրանց մեջտեղի կետը՝ $(26 + 80) / 2$left parenthesis, 26, plus, 80, right parenthesis, slash, 2, այսինքն՝ 53-ը։ Այնուհետև եթե քեզ ասեմ, որ 53-ը շատ մեծ է, 53-ից 80 բոլոր թվերը պետք է բացառես՝ թողնելով 26-ից 52 թվերը՝ որպես տրամաբանական ենթադրությունների նոր միջակայք՝ կիսելով միջակայքի չափը:

«Գուշակիր թիվը» խաղում կռահելու համար մենք հետևում ենք տրամաբանական գուշակումների բազմությանը՝ օգտագործելով մի քանի փոփոխական: Դիցուք, փոփոխական $min$m, i, n-ը տրամաբանական կռահումի նվազագույն միավորն է, իսկ փոփոխական $max$m, a, x-ը տրամաբանական կռահումի առավելագույն միավորն է: Խնդրում մուտքագրվող թիվը $n$n-ն է՝ ամենամեծ թիվը, որ քո մրցակիցը կարող է պահել։ Ենթադրենք՝ ամենափոքր հնարավոր թիվը 1-ն է, բայց ավելի հեշտ կլինի հետագայում ալգորիթմն այնպես փոփոխել, որ երկրորդ մուտքագրումից հնարավոր լինի վերցնել ամենափոքր թիվը։

Ահա քայլ առ քայլ նկարագրություն, թե ինչպես երկուական որոնման միջոցով հաղթել «Գուշակիր թիվը» խաղը.

Հետագայի համար կարող ենք այն ավելի լավ տեսքի բերել՝ մանրամասն նկարագրելով ալգորիթմի համար մուտքագրված արժեքներն ու արդյունքները՝ հստակեցնելով, թե ինչ նկատի ունենք «Գուշակիր թիվը» կամ «Կանգնիր» ասելով։ Բայց առայժմ մեզ մեր ունեցածն էլ բավական է։

Հաջորդիվ կտեսնենք, թե ինչպես կարող ենք օգտագործել երկուական որոնումը զանգվածի դեպքում և կքննարկենք, թե ինչպես ալգորիթմների նկարագրություններից իրական աշխատող կոդ ստանալ։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։