सी ++ प्रोग्राम में बाइनरी सर्च?

द्विआधारी खोज, जिसे अर्ध-अंतराल खोज, लॉगरिदमिक खोज या बाइनरी चॉप के रूप में भी जाना जाता है, एक खोज एल्गोरिथ्म है जो एक क्रमबद्ध सरणी के भीतर लक्ष्य मान की स्थिति का पता लगाता है। बाइनरी खोज लक्ष्य मान की तुलना सरणी के मध्य तत्व से करती है। यदि वे समान नहीं हैं, तो आधा जिसमें लक्ष्य झूठ नहीं बोल सकता है, समाप्त हो जाता है और शेष आधे पर खोज जारी रहती है, फिर से लक्ष्य मान की तुलना करने के लिए मध्य तत्व को लेते हुए, और लक्ष्य मान मिलने तक इसे दोहराते हैं। यदि शेष आधा खाली होने के साथ खोज समाप्त होती है, तो लक्ष्य सरणी में नहीं है। हालांकि यह विचार सरल है, बाइनरी खोज को सही ढंग से कार्यान्वित करने के लिए इसकी निकास स्थितियों और मध्यबिंदु गणना के बारे में कुछ सूक्ष्मताओं पर ध्यान देने की आवश्यकता है, खासकर यदि सरणी में मान श्रेणी में सभी पूर्ण संख्याएं नहीं हैं।

बाइनरी सर्च सबसे लोकप्रिय सर्च एल्गोरिथम है। यह कुशल है और समस्याओं को हल करने के लिए उपयोग की जाने वाली सबसे अधिक उपयोग की जाने वाली तकनीकों में से एक है।

यदि दुनिया के सभी नाम एक साथ क्रम में लिखे गए हैं और आप किसी विशिष्ट नाम की स्थिति खोजना चाहते हैं, तो बाइनरी खोज इसे अधिकतम 35 पुनरावृत्तियों में पूरा करेगी।

बाइनरी सर्च केवल तत्वों के क्रमबद्ध सेट पर काम करता है। किसी संग्रह पर द्विआधारी खोज का उपयोग करने के लिए, संग्रह को पहले क्रमबद्ध किया जाना चाहिए।

जब एक द्विआधारी खोज का उपयोग क्रमबद्ध सेट पर संचालन करने के लिए किया जाता है, तो खोजे जा रहे मूल्य के आधार पर पुनरावृत्तियों की संख्या को हमेशा कम किया जा सकता है।

आइए निम्नलिखित सरणी पर विचार करें -

रेखीय खोज का उपयोग करके, 9वें पुनरावृत्ति में तत्व 8 की स्थिति निर्धारित की जाएगी।

आइए देखें कि द्विआधारी खोज का उपयोग करके पुनरावृत्तियों की संख्या को कैसे कम किया जा सकता है। खोज शुरू करने से पहले, हमें सीमा की शुरुआत और अंत जानने की जरूरत है। चलो उन्हें निम्न और उच्च कहते हैं।

Low = 0
High = n-1

अब, खोज मान K की तुलना निचली और ऊपरी सीमा के मध्य में स्थित तत्व से करें। यदि मान K अधिक है, तो निचली सीमा बढ़ाएँ, अन्यथा ऊपरी सीमा घटाएँ।

ऊपर की छवि के संदर्भ में, निचली सीमा 0 है और ऊपरी सीमा 9 है

निचली और ऊपरी सीमा का माध्यिका (निचला_बाउंड + अपर_बाउंड) / 2 =4 है। यहां एक [4] =4. मान 4> 2 है, जो वह मान है जिसे आप खोज रहे हैं। इसलिए, हमें 4 से आगे के किसी भी तत्व की खोज करने की आवश्यकता नहीं है क्योंकि इससे परे के तत्व स्पष्ट रूप से 2 से अधिक होंगे।

इसलिए, हम हमेशा एरे के ऊपरी बाउंड को एलिमेंट 4 की स्थिति में छोड़ सकते हैं। अब, हम निम्नलिखित मानों के साथ उसी एरे पर एक ही प्रक्रिया का पालन करते हैं -

Low: 0
High: 3

निम्न> उच्च तक इस प्रक्रिया को पुनरावर्ती रूप से दोहराएं। यदि किसी पुनरावृत्ति पर, हमें एक [मध्य] =कुंजी मिलती है, तो हम मध्य का मान लौटाते हैं। यह सरणी में कुंजी की स्थिति है। यदि कुंजी सरणी में मौजूद नहीं है, तो हम -1 लौटाते हैं।

उदाहरण

int binarySearch(int low,int high,int key){
   while(low<=high){
      int mid=(low+high)/2;
      if(a[mid]<key){
         low=mid+1;
      }
      else if(a[mid]>key){
         high=mid-1;
      }
      else{
         return mid;
      }
   }
   return -1; //key not found
}