دا سبق به د بائنری لټون تشریح کړي & په جاوا کې تکراري بائنري لټون د الګوریتم، پلي کولو، او جاوا بائنري سیچ کوډ مثالونه:
په جاوا کې د بائنري لټون یو تخنیک دی چې په ټولګه کې د هدف شوي ارزښت یا کلیدي لټون لپاره کارول کیږي. دا یو تخنیک دی چې د کیلي لټون کولو لپاره د "تقسیم او فتح" تخنیک کاروي.
هغه ټولګه چې د کیلي لټون لپاره د بائنری لټون پلي کیږي باید په پورته ترتیب سره ترتیب شي.
معمولا، د پروګرام کولو ډیری ژبې د خطي لټون، بائنري لټون، او د هاشینګ تخنیکونو ملاتړ کوي چې په ټولګه کې د معلوماتو لټون کولو لپاره کارول کیږي. موږ به زموږ په راتلونکو درسونو کې د هیشینګ زده کړه وکړو.
په جاوا کې د بائنري لټون
خطي لټون یو اساسي تخنیک دی. په دې تخنیک کې، سرې په ترتیب سره تیریږي او هر عنصر د کیلي سره پرتله کیږي تر هغه چې کیلي وموندل شي یا د صف پای ته ورسیږي.
په عملي غوښتنلیکونو کې لینر لټون په ندرت سره کارول کیږي. د بائنري لټون خورا ډیر کارول شوی تخنیک دی ځکه چې دا د خطي لټون په پرتله خورا ګړندی دی.
5>جاوا د بائنری لټون ترسره کولو لپاره درې لارې وړاندې کوي: 1>>7>8>استعمال تکراري کړنلاره
په دې ټیوټوریل کې به موږ دا ټول پلي او بحث وکړو 3 میتودونه.
په جاوا کې د بائنری لټون لپاره الګوریتم
په بائنری کېد لټون طریقه، ټولګه په مکرر ډول په نیمایي ویشل کیږي او کلیدي عنصر د ټولګې په ښي یا ښي نیمه برخه کې لټول کیږي پدې پورې اړه لري چې آیا کیلي د ټولګې د منځني عنصر څخه کم یا لوی دی.
د بائنري لټون یو ساده الګوریتم په لاندې ډول دی:
- د ټولګې منځنی عنصر محاسبه کړئ.
- کلیدي توکي د منځني عنصر سره پرتله کړئ.
- که کیلي = منځنی عنصر، نو موږ د موندل شوي کیلي لپاره د منځنۍ شاخص موقعیت بیرته راګرځوو.
- که کیلي > منځنی عنصر، بیا کلید د ټولګې په ښي نیمایي کې پروت دی. په دې توګه د ټولګې په ښکته (ښي) نیمه برخه کې له 1 څخه تر 3 پورې مرحلې تکرار کړئ.
- بل کیلي منځنی عنصر، بیا کیلي د ټولګې په پورتنۍ نیمایي کې ده. له همدې امله تاسو اړتیا لرئ د بائنري لټون په پورتنۍ نیمایي کې تکرار کړئ.
لکه څنګه چې تاسو د پورته مرحلو څخه لیدلی شئ، په بائنري لټون کې، د راټولولو نیمایي عناصر یوازې د لومړي پرتله کولو وروسته له پامه غورځول کیږي.
په یاد ولرئ چې د ګامونو ورته ترتیب د تکراري او تکراري بائنري لټون لپاره هم شتون لري.
راځئ چې د مثال په کارولو سره د بائنری لټون الګوریتم روښانه کړو.
د مثال په توګه، د 10 عناصرو لاندې ترتیب شوی صف واخلئ.
راځئ چې د سرې منځنی موقعیت محاسبه کړو.
منځ = 0+9/2 = 4
#1) کیلي = 21
لومړی، موږ به د کلیدي ارزښت سره پرتله کړو [mid] عنصر او موږ ګورو چې عنصر ارزښت په کېmid = 21.
په دې توګه موږ هغه کیلي = [میډیا] پیدا کوو. له دې امله کیلي په صف کې په 4 موقعیت کې موندل کیږي.
#2) کیلي = 25
16>1>
موږ لومړی کیلي پرتله کوو ارزښت تر منځ لکه څنګه چې (21 25)، موږ به په مستقیم ډول د سرې په پورتنۍ نیمایي کې کیلي ولټوو.
اوس به بیا د پورتنۍ نیمایي لپاره منځنی پیدا کړو. صف.
منځ = 4+9/2 = 6
په ځای کې ارزښت [میډ] = 25
18>
اوس موږ کلیدي عنصر د منځني عنصر سره پرتله کړئ. نو (25 == 25)، له دې امله موږ کلید په ځای کې موندلی دی [میډ] = 6.
په دې توګه موږ په مکرر ډول سرې ویشو او د کلیدي عنصر د مینځ سره پرتله کولو سره، موږ پریکړه کوو چې په کوم نیم کې د کلیدي لټون. د بائنري لټون د وخت او سموالي له پلوه خورا موثر دی او خورا ګړندی هم دی.
د بائنري لټون پلي کول جاوا
د پورتني الګوریتم په کارولو سره ، راځئ چې په جاوا کې د بائنري لټون برنامې پلي کړو. تکراري تګلاره په دې پروګرام کې، موږ یو مثال اخلو او په دې صف کې د بائنری لټون ترسره کوو.
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
پورته پروګرام د بائنری لټون تکراري طریقه ښیې. په پیل کې، یو صف اعلانیږي، بیا د لټون کولو لپاره کلیدي تعریف کیږي.
د سرې د مینځني حساب کولو وروسته، کیلي د منځني عنصر سره پرتله کیږي. بیا په دې پورې اړه لري چې آیاکیلي د کیلي څخه کم یا لویه وي، کیلي په ترتیب سره د صف په ښکته یا پورتنۍ نیمایي کې پلټنه کیږي.
په جاوا کې تکراري بائنری لټون
تاسو کولی شئ د بائنری لټون هم ترسره کړئ د تکرار تخنیک کارول. دلته، د بائنری لټون طریقه په تکرار سره ویل کیږي تر هغه چې کیلي وموندل شي یا ټول لیست ختم شوی نه وي.
هغه پروګرام چې د تکراري بائنری لټون پلي کوي لاندې ورکړل شوی:
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 () میتود په کارولو سره.
په جاوا کې د 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]
هغه کلیدي چې د لټون وړ دي:50
کیلي په شاخص کې موندل کیږي: 4 په صف کې.
ډیری پوښتل شوي پوښتنې
پوښتنه # 1) تاسو د بائنری لټون څنګه لیکئ؟ ?
ځواب: د بائنري لټون معمولا په نیمو برخو ویشلو سره ترسره کیږي. که د لټون کولو کیلي د منځني عنصر څخه لوی وي،بیا د سرې پورتنۍ نیمه برخه د فرعي سرې د نور ویشلو او لټون کولو سره تر هغه وخته پورې لټول کیږي چې کیلي وموندل شي.
په ورته ډول، که کیلي د منځني عنصر څخه کم وي، نو بیا کیلي په ښکته برخه کې لټون کیږي. د صف نیمه برخه.
پوښتنه #2) د بائنری لټون چیرته کارول کیږي؟
ځواب: د بائنری لټون په عمده توګه د لټون لپاره کارول کیږي د سافټویر غوښتنلیکونو کې ترتیب شوي ډاټا په ځانګړي توګه کله چې د حافظې ځای کمپیکٹ او محدود وي.
پوښتنه #3) د بائنری لټون لوی O څه شی دی؟
ځواب : د بائنری لټون د وخت پیچلتیا O (logn) ده چیرې چې n په صف کې د عناصرو شمیر دی. د بائنری لټون د فضا پیچلتیا O (1) ده.
Q #4) آیا د بائنری لټون تکرار دی؟
ځواب: هو. ځکه چې د بائنری لټون د ویشلو او فتح کولو ستراتیژۍ یوه بیلګه ده او دا د تکرار په کارولو سره پلي کیدی شي. موږ کولی شو سرې په نیمو برخو وویشو او بیا بیا د بائنری لټون ترسره کولو لپاره ورته میتود غږ کړو.
پوښتنه #5) ولې دې ته د بائنری لټون ویل کیږي؟
0 ځواب: د بائنری لټون الګوریتم د ویشلو او فتح کولو ستراتیژي کاروي چې په مکرر ډول سرې په نیمه یا دوه برخو ویشي. په دې توګه دا د بائنری لټون په نوم نومول شوی.پایله
د بائنری لټون په جاوا کې د ډیری وخت د لټون تخنیک دی. د بائنری لټون د ترسره کولو لپاره اړتیا دا ده چې ډاټا باید په پورته ترتیب سره ترتیب شي.
د بائنری لټون کیدای شيد تکراري یا تکراري طریقې په کارولو سره پلي کیږي. په جاوا کې د Arrays ټولګي د 'binarySearch' طریقه هم وړاندې کوي چې په یوه سري کې د بائنری لټون ترسره کوي.
زموږ په راتلونکو درسونو کې، موږ به په جاوا کې د ترتیب کولو مختلف تخنیکونه وپلټو.