Այս ձեռնարկը կբացատրի Երկուական որոնումը & Recursive Binary Search Java-ում իր ալգորիթմի, ներդրման և Java-ի երկուական որոնման կոդի օրինակներ.
Երկուական որոնումը Java-ում տեխնիկա է, որն օգտագործվում է հավաքածուում նպատակային արժեք կամ բանալի որոնելու համար: Սա տեխնիկա է, որն օգտագործում է «բաժանիր և տիրիր» տեխնիկան՝ բանալին որոնելու համար:
Հավաքածուն, որի վրա պետք է կիրառվի Երկուական որոնում բանալի որոնելու համար, պետք է տեսակավորվի աճման կարգով:
Սովորաբար, ծրագրավորման լեզուների մեծ մասն աջակցում է Գծային որոնում, Երկուական որոնում և Հաշինգ տեխնիկա, որոնք օգտագործվում են հավաքածուի տվյալների որոնման համար: Մենք կսովորենք հեշինգը մեր հետագա ձեռնարկներում:
Երկուական որոնում Java-ում
Գծային որոնումը հիմնական տեխնիկա է: Այս տեխնիկայում զանգվածը անցնում է հաջորդաբար և յուրաքանչյուր տարր համեմատվում է բանալիի հետ, մինչև որ գտնվի բանալին կամ հասնի զանգվածի վերջը:
Գծային որոնումը հազվադեպ է օգտագործվում գործնական կիրառություններում: Երկուական որոնումը ամենահաճախ օգտագործվող տեխնիկան է, քանի որ այն շատ ավելի արագ է, քան գծայինը:
Java-ն առաջարկում է երկուական որոնում իրականացնելու երեք եղանակ.
- Օգտագործելով կրկնվող մոտեցումը
- Օգտագործելով ռեկուրսիվ մոտեցում
- Օգտագործելով Arrays.binarySearch () մեթոդը:
Այս ձեռնարկում մենք կիրագործենք և կքննարկենք այս ամենը 3 մեթոդ:
Երկուական որոնման ալգորիթմ Java-ում
Երկուականումորոնման մեթոդով, հավաքածուն բազմիցս բաժանվում է կիսով չափ, և հիմնական տարրը որոնվում է հավաքածուի ձախ կամ աջ կեսում՝ կախված նրանից, թե արդյոք բանալին փոքր է կամ մեծ, քան հավաքածուի միջին տարրը:
Հասարակ Երկուական որոնման ալգորիթմը հետևյալն է.
- Հաշվե՛ք հավաքածուի միջին տարրը։
- Համեմատե՛ք հիմնական տարրերը միջին տարրի հետ։
- Եթե բանալին = միջին տարր, ապա մենք վերադարձնում ենք հայտնաբերված բանալի միջին ինդեքսի դիրքը:
- Else If key > միջին տարրը, ապա բանալին գտնվում է հավաքածուի աջ կեսում: Այսպիսով, կրկնեք 1-ից 3-րդ քայլերը հավաքածուի ստորին (աջ) կեսի վրա:
- Else key միջին տարր, ապա բանալին գտնվում է հավաքածուի վերին կեսում: Այսպիսով, դուք պետք է կրկնեք երկուական որոնումը վերին կեսում:
Ինչպես երևում է վերը նշված քայլերից, Երկուական որոնման մեջ հավաքածուի տարրերի կեսն անտեսվում է հենց առաջին համեմատությունից հետո:
Նկատի ունեցեք, որ քայլերի նույն հաջորդականությունը գործում է ինչպես կրկնվող, այնպես էլ ռեկուրսիվ երկուական որոնման համար:
Եկեք պատկերացնենք երկուական որոնման ալգորիթմը՝ օգտագործելով օրինակ:
Օրինակ, վերցրեք 10 տարրերից բաղկացած հետևյալ տեսակավորված զանգվածը:
Եկեք հաշվենք զանգվածի միջին դիրքը:
Mid = 0+9/2 = 4
#1) բանալի = 21
Նախ, մենք կհամեմատենք հիմնական արժեքը [mid] տարր, և մենք գտնում ենք, որ տարրի արժեքը atmid = 21.
Այսպիսով մենք գտնում ենք, որ բանալին = [mid]: Հետևաբար բանալին գտնվում է զանգվածի 4-րդ դիրքում:
#2) Key = 25
Մենք նախ համեմատում ենք բանալին արժեքը մինչև միջին: Որպես (21 25), մենք ուղղակիորեն կփնտրենք բանալին զանգվածի վերին կեսում:
Այժմ մենք նորից կգտնենք միջնամասը վերին կեսի համար: զանգվածը:
Mid = 4+9/2 = 6
Արժեքը գտնվելու վայրում [mid] = 25
Այժմ մենք համեմատել հիմնական տարրը միջին տարրի հետ: Այսպիսով, (25 == 25), հետևաբար մենք գտել ենք բանալին [mid] = 6 գտնվելու վայրում:
Այսպիսով մենք բազմիցս բաժանում ենք զանգվածը և առանցքային տարրը համեմատելով միջինի հետ՝ որոշում ենք, թե որ կեսին որոնել բանալին: Երկուական որոնումն ավելի արդյունավետ է ժամանակի և ճշգրտության առումով և նույնպես շատ ավելի արագ:
Երկուական որոնման իրականացում Java
Օգտագործելով վերը նշված ալգորիթմը, եկեք իրականացնենք Երկուական որոնման ծրագիր Java-ում` օգտագործելով կրկնվող մոտեցում. Այս ծրագրում մենք վերցնում ենք զանգվածի օրինակ և կատարում ենք երկուական որոնում այս զանգվածում։
import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println("The input array: " + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println("\nKey to be searched=" + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first = last ){ //if the mid key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println("Element is not found!"); } } }
Ելք՝
Մուտքային զանգված՝ [5, 10, 15, 20 , 25, 30, 35]
Որոնելու բանալի=20
Տարրը գտնվում է ինդեքսում՝ 3
Վերոնշյալ ծրագիրը ցույց է տալիս Երկուական որոնման կրկնվող մոտեցումը: Սկզբում հայտարարվում է զանգված, այնուհետև սահմանվում է որոնման ենթակա բանալի:
Զանգվածի միջնամասը հաշվարկելուց հետո բանալին համեմատվում է միջին տարրի հետ: Հետո կախված նրանից, թեբանալին փոքր է կամ մեծ է, քան բանալին, բանալին որոնվում է զանգվածի ստորին կամ վերին կեսում համապատասխանաբար:
Recursive Binary Search Java-ում
Դուք կարող եք նաև կատարել երկուական որոնում օգտագործելով ռեկուրսիայի տեխնիկան: Այստեղ երկուական որոնման մեթոդը կոչվում է ռեկուրսիվ, մինչև բանալին գտնվի կամ ամբողջ ցանկը սպառվի:
Ծրագիրը, որն իրականացնում է ռեկուրսիվ երկուական որոնում, տրված է ստորև.
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray[], int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //if intArray[mid] > key then key is in left half of array if (intArray[mid] > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args[]){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println("Input List: " + Arrays.toString(intArray)); int key = 31; System.out.println("\nThe key to be searched:" + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println("\nKey not found in given list!"); else System.out.println("\nKey is found at location: "+result + " in the list"); } }
Ելք՝
Մուտքագրման ցանկ՝ [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Որոնման ենթակա բանալի :
Բանալին գտնվել է տեղում՝ 3 ցուցակում
Օգտագործելով Arrays.binarySearch () մեթոդը:
Java-ում Arrays դասը տրամադրում է «binarySearch ()» մեթոդ, որն իրականացնում է երկուական որոնում տվյալ զանգվածում: Այս մեթոդը վերցնում է զանգվածը և փնտրվող բանալին որպես արգումենտ և վերադարձնում է բանալու դիրքը զանգվածում: Եթե բանալին չի գտնվել, ապա մեթոդը վերադարձնում է -1:
Ստորև բերված օրինակն իրականացնում է Arrays.binarySearch () մեթոդը:
import java.util.Arrays; class Main{ public static void main(String args[]){ //define an array int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println("The input Array : " + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println("\nThe key to be searched:" + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result 0) System.out.println("\nKey is not found in the array!"); else System.out.println("\nKey is found at index: "+result + " in the array."); } }
Ելք.
Մուտքային զանգված. [10, 20, 30, 40, 50, 60, 70, 80, 90]
Որոնվող բանալի:>Բանալին գտնվում է զանգվածում` 4 ինդեքսում:
Հաճախակի տրվող հարցեր
Հ #1) Ինչպես եք գրում երկուական որոնում ?
Պատասխան. Երկուական որոնումը սովորաբար կատարվում է զանգվածը կիսով չափ բաժանելով: Եթե որոնվող բանալին ավելի մեծ է, քան միջին տարրը,ապա զանգվածի վերին կեսը որոնվում է ենթազանգվածը հետագա բաժանելով և որոնելով մինչև բանալին գտնվի:
Նմանապես, եթե բանալին փոքր է միջին տարրից, ապա բանալին որոնվում է ստորին մասում: զանգվածի կեսը:
Հ #2) Որտե՞ղ է օգտագործվում երկուական որոնումը:
Պատասխան. Երկուական որոնումը հիմնականում օգտագործվում է որոնման համար տեսակավորված տվյալները ծրագրային հավելվածներում, հատկապես, երբ հիշողության տարածքը կոմպակտ է և սահմանափակ:
Հ #3) Ո՞րն է երկուական որոնման մեծ O-ն:
Պատասխան : Երկուական որոնման ժամանակային բարդությունը O (logn) է, որտեղ n-ը զանգվածի տարրերի թիվն է: Երկուական որոնման տիեզերական բարդությունը O (1) է։
Q #4) Արդյո՞ք երկուական որոնումը ռեկուրսիվ է։
Պատասխան՝ Այո։ Քանի որ երկուական որոնումը բաժանիր և տիրիր ռազմավարության օրինակ է և այն կարող է իրականացվել ռեկուրսիայի միջոցով: Մենք կարող ենք զանգվածը կիսել կիսով չափ և կանչել նույն մեթոդը՝ կրկնակի որոնումը կրկին ու կրկին կատարելու համար:
Հ #5) Ինչո՞ւ է այն կոչվում երկուական որոնում:
Պատասխան․ Երկուական որոնման ալգորիթմը օգտագործում է բաժանիր և տիրիր ռազմավարությունը, որը բազմիցս բաժանում է զանգվածը կիսով չափ կամ երկու մասի։ Այսպիսով, այն կոչվում է երկուական որոնում:
Եզրակացություն
Երկուական որոնումը Java-ում հաճախակի օգտագործվող որոնման տեխնիկան է: Երկուական որոնման պահանջն այն է, որ տվյալները պետք է դասավորված լինեն աճման կարգով:
Երկուական որոնումը կարող է լինել.իրականացվում է կրկնվող կամ ռեկուրսիվ մոտեցման միջոցով: Զանգվածների դասը Java-ում տրամադրում է նաև «binarySearch» մեթոդը, որն իրականացնում է երկուական որոնում զանգվածի վրա:
Մեր հետագա ձեռնարկներում մենք կուսումնասիրենք Java-ում տեսակավորման տարբեր տեխնիկա: