binary search algorithm java implementation examples
यह ट्यूटोरियल जावा में अपने एल्गोरिथ्म, कार्यान्वयन और जावा बाइनरी सीच कोड उदाहरणों के साथ बाइनरी खोज और पुनरावर्ती बाइनरी खोज की व्याख्या करेगा:
जावा में एक द्विआधारी खोज एक तकनीक है जिसका उपयोग संग्रह में लक्षित मूल्य या कुंजी की खोज करने के लिए किया जाता है। यह एक ऐसी तकनीक है जो एक कुंजी को खोजने के लिए 'डिवाइड और जीतना' तकनीक का उपयोग करती है।
जिस संग्रह पर द्विआधारी खोज को लागू किया जाना है, उसे एक प्रमुख आवश्यकता के लिए आरोही क्रम में क्रमबद्ध किया जाना चाहिए।
आमतौर पर, प्रोग्रामिंग की अधिकांश भाषाएं रैखिक खोज, बाइनरी खोज और हैशिंग तकनीकों का समर्थन करती हैं जो संग्रह में डेटा की खोज के लिए उपयोग की जाती हैं। हम अपने बाद के ट्यूटोरियल में हैशिंग सीखेंगे।
=> स्क्रैच से जावा सीखने के लिए यहां जाएं।
आप क्या सीखेंगे:
बाइनरी सर्च इन जावा
रैखिक खोज एक बुनियादी तकनीक है। इस तकनीक में, सरणी को क्रमिक रूप से ट्रेस किया जाता है और प्रत्येक तत्व को कुंजी की तुलना की जाती है जब तक कि कुंजी नहीं मिल जाती है या सरणी के अंत तक नहीं पहुंच जाती है।
रैखिक अनुप्रयोगों का उपयोग शायद ही कभी व्यावहारिक अनुप्रयोगों में किया जाता है। बाइनरी खोज सबसे अधिक उपयोग की जाने वाली तकनीक है क्योंकि यह रैखिक खोज की तुलना में बहुत तेज है।
बाइनरी खोज करने के लिए जावा तीन तरीके प्रदान करता है:
वेब सेवाओं के परीक्षण का उपयोग करके साबुनूई साक्षात्कार प्रश्न
- पुनरावृत्त दृष्टिकोण का उपयोग करना
- पुनरावर्ती दृष्टिकोण का उपयोग करना
- Arrays.binarySearch () पद्धति का उपयोग करना।
इस ट्यूटोरियल में, हम इन 3 तरीकों को लागू करेंगे और चर्चा करेंगे।
बाइनरी के लिए एल्गोरिथ्म जावा में खोज
द्विआधारी खोज विधि में, संग्रह को बार-बार आधे में विभाजित किया जाता है और संग्रह के मध्य तत्व से कम या अधिक होने के आधार पर संग्रह के बाएं या दाएं आधे हिस्से में कुंजी तत्व को खोजा जाता है।
एक सरल बाइनरी खोज एल्गोरिथम इस प्रकार है:
- संग्रह के मध्य तत्व की गणना करें।
- मध्य तत्व के साथ प्रमुख वस्तुओं की तुलना करें।
- यदि कुंजी = मध्य तत्व, तो हम पाया कुंजी के लिए मध्य सूचकांक स्थिति वापस करते हैं।
- और यदि कुंजी> मध्य तत्व, तो कुंजी संग्रह के दाईं ओर स्थित है। इस प्रकार संग्रह के निचले (दाएं) आधे भाग पर चरण 1 से 3 दोहराएं।
- और चाबी
जैसा कि आप उपरोक्त चरणों से देख सकते हैं, बाइनरी सर्च में, संग्रह के आधे तत्वों को पहली तुलना के बाद ही नजरअंदाज कर दिया जाता है।
ध्यान दें कि चरणों का समान अनुक्रम पुनरावृत्ति के साथ-साथ पुनरावर्ती बाइनरी खोज के लिए भी है।
एक उदाहरण का उपयोग करके द्विआधारी खोज एल्गोरिदम का उदाहरण दें।
उदाहरण के लिए, निम्नलिखित 10 तत्वों की क्रमबद्ध सरणी लें।
सरणी के मध्य स्थान की गणना करते हैं।
मध्य = ० + ९ / २ = ४
(१) की = २१
सबसे पहले, हम मुख्य मूल्य की तुलना (मध्य) तत्व के साथ करेंगे और हम पाते हैं कि तत्व का मूल्य मध्य = 21 है।
इस प्रकार हम वह कुंजी = (मध्य) पाते हैं। इसलिए कुंजी सरणी में स्थिति 4 पर पाई जाती है।
# 2) की = 25
हम पहले मुख्य मूल्य की तुलना मध्य में करते हैं। यथा (२१)<25), we will directly search for the key in the upper half of the array.
अब फिर से हम सरणी के ऊपरी आधे भाग के लिए मध्य पाएंगे।
अनुभवी के लिए शुद्ध साक्षात्कार प्रश्न और उत्तर
मध्य = ४ + ९ / २ = ६
स्थान पर मूल्य (मध्य) = २५
अब हम प्रमुख तत्व की तुलना मध्य तत्व से करते हैं। तो (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('
Key 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('
The 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('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } } आउटपुट:
इनपुट सूची: (१, ११, २१, ३१, ४१, ५१, ६१, ,१, ,१, ९ १
खोजे जाने की कुंजी:
सूची में कुंजी स्थान 3 पर पाई गई है
Arrays.binarySearch () पद्धति का उपयोग करना।
जावा में एरेस वर्ग एक r बाइनरीसर्च () विधि प्रदान करता है जो दिए गए एरे पर द्विआधारी खोज करता है। यह विधि सरणी और कुंजी को तर्क के रूप में खोजा जाता है और सरणी में कुंजी की स्थिति देता है। यदि कुंजी नहीं मिली है, तो विधि -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('
The 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('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } } आउटपुट:
इनपुट ऐरे: (10, 20, 30, 40, 50, 60, 70, 80, 90)
खोजी जाने वाली कुंजी: 50
सूचकांक में कुंजी पाई जाती है: सरणी में 4।
बार बार पूछे जाने वाले प्रश्न
Q # 1) आप बाइनरी सर्च कैसे लिखते हैं?
सैमसंग हॉटस्पॉट के लिए नेटवर्क सुरक्षा कुंजी
उत्तर: बाइनरी खोज को आमतौर पर एरे को हिस्सों में विभाजित करके किया जाता है। यदि खोज की जाने वाली कुंजी मध्य तत्व से अधिक है, तो सरणी के ऊपरी आधे हिस्से को आगे विभाजित करके और उप-सरणी की खोज तब तक की जाती है जब तक कुंजी नहीं मिल जाती है।
इसी तरह, यदि कुंजी मध्य तत्व से कम है, तो सरणी के निचले आधे हिस्से में कुंजी की खोज की जाती है।
Q # 2) बाइनरी खोज का उपयोग कहां किया जाता है?
उत्तर: बाइनरी खोज मुख्य रूप से सॉफ़्टवेयर अनुप्रयोगों में सॉर्ट किए गए डेटा को खोजने के लिए उपयोग किया जाता है, खासकर जब मेमोरी स्पेस कॉम्पैक्ट और सीमित होती है।
Q # 3) बाइनरी सर्च का बड़ा O क्या है?
उत्तर: बाइनरी खोज की समय जटिलता हे (लॉगन) है जहां n सरणी में तत्वों की संख्या है। बाइनरी खोज की अंतरिक्ष जटिलता हे (1) है।
Q # 4) क्या द्विआधारी खोज पुनरावर्ती है?
उत्तर: हाँ। चूंकि द्विआधारी खोज एक विभाजित और जीत की रणनीति का एक उदाहरण है और इसे पुनरावृत्ति का उपयोग करके लागू किया जा सकता है। हम सरणी को हिस्सों में विभाजित कर सकते हैं और बाइनरी सर्च को बार-बार करने के लिए उसी विधि को कॉल कर सकते हैं।
Q # 5) इसे बाइनरी सर्च क्यों कहा जाता है?
उत्तर: द्विआधारी खोज एल्गोरिथ्म एक विभाजित और जीत की रणनीति का उपयोग करता है जो बार-बार सरणी को आधा या दो भागों में काटता है। इस प्रकार इसे बाइनरी सर्च का नाम दिया गया है।
निष्कर्ष
बाइनरी खोज जावा में अक्सर उपयोग की जाने वाली खोज तकनीक है। बाइनरी खोज करने के लिए आवश्यकता यह है कि डेटा को आरोही क्रम में क्रमबद्ध किया जाना चाहिए।
एक द्विआधारी खोज को पुनरावृत्त या पुनरावर्ती दृष्टिकोण का उपयोग करके लागू किया जा सकता है। जावा में एरेस वर्ग ays बाइनरीसर्च ’विधि भी प्रदान करता है जो एक ऐरे पर एक बाइनरी खोज करता है।
हमारे बाद के ट्यूटोरियल में, हम जावा में विभिन्न सॉर्टिंग तकनीकों का पता लगाएंगे।
=> यहाँ सरल जावा प्रशिक्षण श्रृंखला देखें।
अनुशंसित पाठ
- चयन सॉर्ट इन जावा - चयन सॉर्ट एल्गोरिथम और उदाहरण
- सम्मिलन क्रमबद्ध जावा में - सम्मिलन क्रमबद्ध एल्गोरिथ्म और उदाहरण
- बाइनरी सर्च ट्री सी ++: BST कार्यान्वयन और उदाहरण के साथ संचालन
- उदाहरण के साथ जावा इंटरफेस और एब्सट्रैक्ट क्लास ट्यूटोरियल
- जावा ट्यूटोरियल फॉर बिगिनर्स: 100+ हैंड्स-ऑन जावा वीडियो ट्यूटोरियल
- जावा में बबल सॉर्ट - जावा सॉर्टिंग एल्गोरिदम और कोड उदाहरण
- जावा स्ट्रिंग ट्यूटोरियल | उदाहरण के साथ जावा स्ट्रिंग के तरीके
- जावा वेक्टर क्या है | उदाहरणों के साथ जावा वेक्टर क्लास ट्यूटोरियल