How Binary Search Works.hy.md

Բինար որոնման ալգորիթմը: Ո՞րն է բինար և գծային որոնման ալգորիթմերի տարբերությունը: JavaScript ծրագրավորման լեզվի միջոցով ստեղծենք ֆունկցիա, որն օգտագործելով ԲԻՆԱՐ ՈՐՈՆՄԱՆ ԱԼԳՈՐԻԹՄԸ՝ թվերի տեսակավորված զանգվածի մեջից կգտնի և կվերադարձնի որոնվող էլեմենտի ինդեքսը:

Պատկերացնենք թե մեզ անհրաժեշտ է անգլերեն-հայերեն բառարանի մեջ որոնել middle բառի նշանակությունը։ Ի՞նչ մեթոդաբանություն կօգտագործենք այդ որոնումը հնարավորինս արագ անելու համար։ Մենք իհարկե կարող ենք բացել բառարանը և սկզբից էջ առ էջ կարդալով առաջ շարժվել, մինչև հասնենք middle բառին։ Սակայն դա կլինի շատ երկար և ձանձրալի զբաղմունք, որովհետև մի քանի տասնյակ հազար բառերից բաղկացած բառարանի մեջ խելամիտ չի լինի նման մեթոդաբանությամբ որոնել անհրաժեշտ բառը։

Որոնումն ավելի արագ կատարելու համար ճիշտ կլինի բառարանը բացել ինչ-որ տեղ գրքի կեսից, չէ որ m տառը այբուբենի մոտավորապես մեջտեղում է գտնվում։ Եվ արդեն մեջտեղից բացելու դեպքում եթե տեսնենք որ օրինակ n տառով բառերն են, մենք հաստատ գիտենք որ այդ էջից սկսած մինչև բառարանի վերջին էջը մեզ այլևս պետք չէ ման գալ middle բառը, քանի-որ n տառը հաջորդում է m տառին, և հետևաբար middle բառը պետք է լինի բառարանի առաջին կեսի մեջ։

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

Վերցնենք մեկ ուրիշ օրինակ՝ թվերի տեսակավորված զանգված։ Օրինակ՝ [1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 40, 80, 100, 120, 134, 170]: Ենթադրենք մենք որոնում ենք 10 թիվը, որը գտնվում է 5 ինդեքսում։ Եթե օգտվենք առաջին մեթոդաբանությունից, մենք պետք է զանգվածի էլէմենտները հերթով ստուգելով առաջ շարժվենք, մինչև գտնենք մեզ անհրաժեշտ 10 թիվը։ Մենք այն կգտնենք 6-րդ քայլից, սակայն այս դեպքում մեր բախտը մի փոքր բերել է։ Իսկ եթե մեզ անհրաժեշտ լիներ որոնել 170 թիվը՞։ Դա վատագույն տարբերակն է, և մենք այն կգտնեյինք 16-րդ քայլից։ Զանգվածը բաղկացած է 16 էլէմենտից և վատագույն դեպքում մենք որոնվող էլեմենտը գտանք 16-րդ քայլից։ Եթե զանգվածը բաղկացած լիներ 1000 էլէմենտից, վատագույն դեպքում մենք ստիպված ենք լինելու 1000 էլեմենտ հատ առ հատ, հերթով ստուգել։ Այս մեթոդաբանության մեջ մենք օգտագործեցինք գծային որոնման ալգորիթմը, որը ենթադրում է հերթով հատ առ հատ ստուգել որոնման ենթակա ցուցակը, պահանջվող էլեմենտը գտնելու համար։ Այսինքն եթե ունենք n քանակի էլեմենտներ, մենք ստիպված ենք լինելու վատագույն դեպքում կատարել n քանակի համեմատություններ, մինչև գտնենք որոնվող էլեմենտը։ Այս ալգորիթմի բարդությունը հետևաբար կլինի O(n):

Երկրորդ մեթոդաբանությունը կառուցվում է լիովին այլ՝ բինար որոնման ալգորիթմի վրա։ Եվ եթե մեզ պետք է այդ զանգվածի 5-րդ ինդեքսում գտնվող 10 թիվը, մենք կարող ենք ստուգել զանգվածի մոտավորապես մեջտեղում գտնվող էլեմենտը։ Կանգ կառնենք 7-րդ ինդեքսում գտնվող 12 թվի վրա։ Այն ավելի մեծ է, քան մեր որոնած 10 թիվը, հետևաբար 12-ից աջ ընկած թվերը մեզ այլևս պետք չեն, դրանք բոլորը հաստատ մեծ են 10-ից։ Ստացվում է, որ հենց առաջին քայլից մենք թեև չգտանք այն էլեմենտը, որը փնտրում էինք, սակայն կիսով չափ կրճատեցինք որոնման ենթակա էլեմենտների քանակը։ Շարունակենք նույն տրամաբանությամբ, արդեն կիսված զանգվածի մեջ ընտրենք մոտավորապես մեջտեղում գտնվող էլեմենտը։ Կանգ առնենք 5 թվի վրա, որը գտնվում է 3 ինդեքսում։ Մեր որոնած 10 թիվը ավելի մեծ է, քան 3 ինդեքսում գտնվող 5 թիվը, հետևաբար 3 ինդեքսից ձախ գտնվող էլեմենտները մեզ նույնպես պետք չեն, նրանք հաստատ ավելի փոքր են որոնվող թվից։ Դեն ենք նետում արդեն նախնական զանգվածի կեսի ևս մի կեսը։ Որոնման ենթակա էլեմենտների քանակն արդեն պակասեց 3/4-ով։

Մնացած զանգվածի մեջ կրկին վերցնենք մոտավորապես մեջտեղում գտնվող էլեմենտը, այն կլինի 10-ը, որը գտնվում է 5-րդ ինդեքսում, և որն էլ պահանջվում էր գտնել։ (Քանի-որ զանգվածի էլեմենտների քանակը զույգ է, ուղիղ մեջտեղում գտնվող մի էլեմենտ չկա, և մեջտեղում գտնվող երկու էլեմենտներից ես միշտ որպես «հենման կետ» ընտրել եմ փոքր ինդեքս ունեցողը, օրինակ վերջին քայլի մեջ երբ մնում է [8, 10, 11, 12] էլեմենտներից բաղկացած զանգվածը, մեջտեղում գտնվող 10 և 11 էլեմենտների մեջից ընտրել եմ ավելի ցածր ինդեքսով 10 թիվը։)

Բինար որոնման ալգորիթմն անհամեմատ արդյունավետ է։ Եթե գծային որոնման ալգորիթմի կիրառման պարագայում մենք n թվով էլեմենտների առկայության դեպքում ստիպված ենք վատագույն տարբերակում n անգամ կատարել համեմատություններ, մինչև գտնենք որոնվող էլեմենտը, ապա բինար որոնման ալգորիթմի կիրառության դեպքում մենք այդ արդյունքը կստանանք log₂ⁿ քանակի համեմատություններ անելով։ Այսինքն բինար որոնման ալգորիթմի բարդությունը կազմում է O(log₂ⁿ)։

Մեր վերևի օրինակի թվերի տեսակավորված զանգվածը բաղկացած է 16 էլեմենտից։ Գծային որոնման ալգորիթմ օգտագործելով մենք պահանջվող էլեմենտը կգտնենք վատագույն դեպքում 16 քայլից։ Բինար որոնման ալգորիթմը պահանջվող էլեմենտը կգտնի log₂¹⁶ քայլից։ log₂¹⁶-ը հավասար է 4-ի, հետևաբար նույնիսկ ամենաանբարենպատ դիրքում մենք ցանկացած էլեմենտը կգտնենք 4 քայլից։

Հետաքրքիրն այն է, որ ինչքան զանգվածի չափերը մեծ է, այնքան այդ ալգորիթմերի արտադրողականության տարբերությունը ահռելի է դառնում։ Օրինակ եթե զանգվածը բաղկացած է 240,000 էլեմենտից՝ տրված էլեմենտը գտնելու համար գծային որոնման դեպքում անհրաժեշտ կլինի վատագույն դեպքում կատարել 240,000 քայլ։ Այնինչ բինար որոնման համար բավարար է ընդամենը 18 քայլը, որովհետև log₂²⁴⁰⁰⁰⁰-ը մոտավորապես հավասար է 18-ի (17,87․․․ պետք է միշտ կլորացնենք դեպի մոտակա մեծ ամբողջ թիվը)։ Համաձայնեք՝ տարբերությունը շշմեցուցիչ է։ Ինչպես արդեն հասկացանք՝ զանգվածը պետք է ՊԱՐՏԱԴԻՐ տեսակավորված լինի։ Հակառակ դեպքում անհնար է կիրառել բինար որոնման ալգորիթմը։

Այժմ փորձենք JavaScript ծրագրավորման լեզվի միջոցով ստեղծել բինար որոնման ալգորիթմի վրա հիմնված ֆունկցիա, որը որպես արգումենտ ստանալով թվերի տեսակավորված զանգված և որոնվող էլեմենտը՝ մեզ կվերադարձնի որոնվող էլեմենտի ինդեքսը։ Եթե թիվը զանգվածում չկա, թող վերադարձնի -1, ինչպես սովորաբար ընդունված է։

function binarySearch(sortedArray, key) {
  let start = 0;
  let end = sortedArray.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);

    if (sortedArray[middle] === key) {
      return middle;
    } else if (sortedArray[middle] < key) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }

  return -1;
}

Հիմա քայլ առ քայլ նայենք, թե ինչպես է ֆունկցիան իրականացնում բինար որոնման ալգորիթմը։ Հայտարարում ենք ֆունկցիա, որն ունի երկու պարամետր՝ sortedArray անունով տեսակավորված զանգվածը, որտեղ պետք է որոնումը կատարենք, և key անունով էլեմենտը, որի ինդեքսն էլ պահանջվում է գտնել sortedArray զանգվածի մեջ։ Ֆունկցիայի մեջ հայտարարում ենք 2 փոփոխականներ՝ start, որին տալիս ենք 0 նախնական արժեքը, քանի որ զանգվածի էլեմենտների ինդեքսը սկսվում է 0-ով, և end` որին որպես նախնական արժեք տալիս ենք զանգվածի վերջին էլեմենտի ինդեքսը՝ sortedArray.length - 1։

Հաջորդը ստեղծում ենք while ցիկլը, իսկ որպես ցիկլի պայման նշում ենք, որ քանի դեռ start-ը փոքր կամ հավասար է end-ին, թող ցիկլն աշխատի։ Այժմ մեզ անհրաժեշտ է լինելու նոր փոփոխական, որն իր մեջ կպահի զանգվածի մոտավորապես մեջտեղում գտնվող էլեմենտի ինդեքսը։ Դրա համար հայտարարում ենք middle անունով փոփոխական, և նրան որպես սկզբնական արժեք վերագրում ենք հետևյալ արտահայտությունը՝ Math.floor((start + end) / 2) ։ Ինչու ենք այստեղ օգտագործում ներդրված Math.floor մեթոդը՝ որպեսզի եթե զանգվածի էլեմենտների քանակը զույգ լինի, այն կլորացվի դեպի ներքև, դեպի ավելի ցածր ինդեքս, և այդ ինդեքսում գտնվող էլեմենտն ընդունվի որպես զանգվածի մեջտեղում գտնվող։

Ապա ստեղծում ենք if պայմանի կոնստրուկցիան, որը ստանալով զանգվածի մեջտեղում գտնվող _sortedArray[middle] _ էլեմենտը՝ կհամեմատի այն key պարամետրով ստացված արժեքի հետ և համընկնելու դեպքում կվերադարձնի middle-ի արժեքը, որը ինչպես հիշում ենք զանգվածի մեջտեղում գտնվող էլեմենտի ինդեքսն է։

Եթե if-ի պայմանը բավարարված չէ, ապա կստուգվի else if-ի պայմանը՝ sortedArray[middle] < key, և եթե այն վերադարձնի true, նշանակում է, որ մենք պետք է փոխենք start-ի արժեքը, վերագրելով նրան middle + 1, որովհետև զանգվածի մեջտեղից դեպի ձախ ընկած ոչ մի էլեմենտ այլևս չի կարող լինել մեր որոնած key էլեմենտին հավասար, նրանց բոլորի արժեքը հաստատ փոքր է key-ի արժեքից։

Եթե ոչ if-ի, ոչ else if-ի պայմանները չեն բավարարվում, նշանակում է, որ մեր որոնած թիվը փոքր է զանգվածի այն էլեմենտից, որի ինդեքսը middle փոփոխականի արժեքն է։ Հետևաբար այլևս անիմաստ է որոնել key էլեմենտը զանգվածի middle ինդեքսով էլեմենտից աջ։ Այնտեղ բոլոր թվերը հաստատ ավելի մեծ են մեր key-ի արժեքից։ Եվ այս դեպքում ոչինչ չի մնում անելու, քան թարմացնել end փոփոխականի արժեքը, նրան վերագրելով middle - 1, որպեսզի որոնումը շարունակվի զանգվածի ձախ կեսի մեջ։

Այդպես կշարունակվի այնքան ժամանակ, քանի դեռ ցիկլի մարմնում գտնվող if-ի պայմանը չի կատարվել, այսինքն key արգումենտի և զանգվածի որևէ էլեմենտի արժեքները չեն համընկնել։ Եթե որևէ համընկնում չկա, իսկ start-ի և end-ի արժեքներն ամեն իտերացիայի ժամանակ թարմացվելով արդեն չեն բավարարում ցիկլի պայմանին, ապա ցիկլը բնականաբար կընդհատվի, առանց արդյունքի, իսկ ֆունկցիայի վերջին տողում գրված return հրահանգը կվերադարձնի -1, որն ընդունված է համարել զանգվածի մեջ որոնվող էլեմենտի բացակայության ինդիկատոր։

Մենք իհարկե հեշտությամբ կարող ենք ֆունկցիան մի փոքր ձևափոխել, որպեսզի այն որոնվող էլեմենտի ինդեքսի փոխարեն վերադարձնի Բուլյան արժեք՝ true՝ եթե զանգվածը պարունակում է այդ էլեմենտը, իսկ հակառակ պարագայում՝ false: Ցանկացողները կարող են դա ինքնուրույն անել: