हे ट्यूटोरियल बायनरी शोध आणि & Java मध्ये रिकर्सिव बायनरी शोध त्याच्या अल्गोरिदम, अंमलबजावणी आणि Java बायनरी शोध कोड उदाहरणे:
जावा मधील बायनरी शोध हे एक तंत्र आहे जे संग्रहातील लक्ष्यित मूल्य किंवा की शोधण्यासाठी वापरले जाते. हे एक तंत्र आहे जे की शोधण्यासाठी “विभाजित करा आणि जिंका” तंत्राचा वापर करते.
की शोधण्यासाठी ज्या संग्रहावर बायनरी शोध लागू करायचा आहे ते चढत्या क्रमाने क्रमवारी लावणे आवश्यक आहे.
सामान्यतः, बहुतेक प्रोग्रामिंग भाषा रेखीय शोध, बायनरी शोध आणि हॅशिंग तंत्रांना समर्थन देतात ज्या संग्रहातील डेटा शोधण्यासाठी वापरल्या जातात. आपण पुढील ट्युटोरियलमध्ये हॅशिंग शिकू.
जावामध्ये बायनरी सर्च
लिनियर सर्च हे एक मूलभूत तंत्र आहे. या तंत्रात, अॅरे क्रमाक्रमाने ट्रॅव्हर्स केला जातो आणि की सापडेपर्यंत किंवा अॅरेचा शेवट होईपर्यंत प्रत्येक घटकाची कीशी तुलना केली जाते.
व्यावहारिक अनुप्रयोगांमध्ये रेखीय शोध क्वचितच वापरला जातो. बायनरी शोध हे सर्वात जास्त वापरले जाणारे तंत्र आहे कारण ते रेखीय शोधापेक्षा खूप वेगवान आहे.
जावा बायनरी शोध करण्यासाठी तीन मार्ग प्रदान करते:
- वापरणे पुनरावृत्तीचा दृष्टीकोन
- पुनरावर्ती दृष्टीकोन वापरणे
- Arrays.binarySearch () पद्धत वापरणे.
या ट्यूटोरियलमध्ये, आपण या सर्वांची अंमलबजावणी आणि चर्चा करू. 3 पद्धती.
जावामध्ये बायनरी शोधासाठी अल्गोरिदम
बायनरीमध्येशोध पद्धत, संग्रह वारंवार अर्ध्या भागांमध्ये विभागला जातो आणि की संग्रहाच्या मध्य घटकापेक्षा कमी किंवा जास्त आहे यावर अवलंबून संग्रहाच्या डाव्या किंवा उजव्या अर्ध्या भागात मुख्य घटक शोधला जातो.
साधा बायनरी शोध अल्गोरिदम खालीलप्रमाणे आहे:
- संग्रहाच्या मध्य घटकाची गणना करा.
- मुख्य घटकांची मध्य घटकाशी तुलना करा.
- की = मधला घटक असल्यास, सापडलेल्या कीसाठी आपण मध्य निर्देशांक स्थान देतो.
- अन्यथा जर की > मध्य घटक, नंतर की संग्रहाच्या उजव्या अर्ध्या भागात आहे. अशा प्रकारे संग्रहाच्या खालच्या (उजवीकडे) अर्ध्या भागावर चरण 1 ते 3 पुन्हा करा.
- अन्यथा की मध्य घटक, नंतर की संग्रहाच्या वरच्या अर्ध्या भागात आहे. त्यामुळे तुम्हाला वरच्या अर्ध्या भागात बायनरी शोधाची पुनरावृत्ती करावी लागेल.
जसे तुम्ही वरील पायऱ्यांवरून पाहू शकता, बायनरी शोधात, संग्रहातील अर्धे घटक पहिल्या तुलनेनंतरच दुर्लक्षित केले जातात.
लक्षात घ्या की स्टेपचा समान क्रम पुनरावृत्ती तसेच पुनरावृत्ती होणार्या बायनरी शोधासाठी आहे.
एक उदाहरण वापरून बायनरी शोध अल्गोरिदम स्पष्ट करू.
उदाहरणार्थ, 10 घटकांची खालील क्रमवारी लावलेली अॅरे घ्या.
चला अॅरेचे मधले स्थान मोजू.
मध्य = 0+9/2 = 4
#1) की = 21
प्रथम, आपण की मूल्याशी तुलना करू [मध्य] घटक आणि आम्हाला आढळते की घटक मूल्य येथे आहेmid = 21.
अशा प्रकारे आपल्याला ती की = [मध्य] सापडते. त्यामुळे अॅरेमध्ये की 4 क्रमांकावर आढळते.
#2) की = 25
आम्ही प्रथम कीची तुलना करतो. मूल्य ते मध्य. (21 25), आम्ही अॅरेच्या वरच्या अर्ध्या भागात थेट की शोधू.
आता पुन्हा आपल्याला वरच्या अर्ध्या भागासाठी मध्य सापडेल अॅरे.
मध्य = 4+9/2 = 6
स्थानावरील मूल्य [मध्य] = 25
आता आम्ही मुख्य घटकाची मध्य घटकाशी तुलना करा. तर (25 == 25), म्हणून आम्हाला स्थान [मध्य] = 6 येथे सापडले आहे.
अशा प्रकारे आपण अॅरेला वारंवार विभाजित करतो आणि मध्याशी की घटकाची तुलना करून, आपण ठरवतो की कोणत्या अर्ध्यामध्ये करायचे की शोधा. बायनरी शोध वेळ आणि अचूकतेच्या दृष्टीने अधिक कार्यक्षम आहे आणि ते खूप जलद देखील आहे.
बायनरी शोध अंमलबजावणी 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
वरील कार्यक्रम बायनरी शोधाचा पुनरावृत्तीचा दृष्टीकोन दर्शवितो. सुरुवातीला, अॅरे घोषित केला जातो, नंतर शोधण्यासाठी की परिभाषित केली जाते.
अॅरेच्या मध्याची गणना केल्यानंतर, कीची मध्य घटकाशी तुलना केली जाते. मग यावर अवलंबून आहे की नाहीकी पेक्षा कमी किंवा जास्त आहे, की क्रमशः अॅरेच्या खालच्या किंवा वरच्या अर्ध्या भागात शोधली जाते.
जावामध्ये रिकर्सिव बायनरी शोध
तुम्ही बायनरी शोध देखील करू शकता पुनरावृत्ती तंत्र वापरून. येथे, की सापडेपर्यंत किंवा संपूर्ण यादी संपेपर्यंत बायनरी शोध पद्धतीला रिकर्सिवली म्हटले जाते.
पुनरावर्ती बायनरी शोध लागू करणारा प्रोग्राम खाली दिलेला आहे:
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 () पद्धत वापरून.
जावा मधील अॅरे वर्ग 'बायनरीसर्च ()' पद्धत प्रदान करतो जी दिलेल्या अॅरेवर बायनरी शोध करते. ही पद्धत वितर्क म्हणून शोधली जाणारी अॅरे आणि की घेते आणि अॅरेमधील कीची स्थिती परत करते. जर की सापडली नाही, तर पद्धत -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 (लॉगन) आहे जिथे n ही अॅरेमधील घटकांची संख्या आहे. बायनरी शोधाची स्पेस कॉम्प्लेक्सिटी O (1) आहे.
प्र #4) बायनरी शोध आवर्ती आहे का?
उत्तर: होय. बायनरी शोध हे विभाजन आणि जिंकण्याच्या रणनीतीचे उदाहरण आहे आणि ते पुनरावृत्ती वापरून लागू केले जाऊ शकते. आपण अॅरेला अर्ध्या भागात विभाजित करू शकतो आणि बायनरी शोध पुन्हा पुन्हा करण्यासाठी त्याच पद्धतीला कॉल करू शकतो.
प्र # 5) याला बायनरी शोध का म्हणतात?
0 उत्तर:बायनरी शोध अल्गोरिदम विभाजित आणि जिंकण्याची रणनीती वापरते जी वारंवार अॅरेला अर्धे किंवा दोन भागांमध्ये कापते. त्यामुळे त्याला बायनरी शोध असे नाव देण्यात आले आहे.निष्कर्ष
बायनरी शोध हे जावामध्ये वारंवार वापरले जाणारे शोध तंत्र आहे. बायनरी शोध करणे आवश्यक आहे की डेटा चढत्या क्रमाने लावला जावा.
बायनरी शोध असू शकतोएकतर पुनरावृत्ती किंवा पुनरावर्ती दृष्टीकोन वापरून अंमलात आणले. Java मधील Arrays क्लास 'binarySearch' पद्धत देखील प्रदान करते जी Array वर बायनरी शोध करते.
आमच्या पुढील ट्युटोरियल्समध्ये, आपण Java मधील विविध क्रमवारी तंत्रे शोधू.