DAA - बाइनरी सर्च

इस अध्याय में, हम फूट डालो और जीतो विधि पर आधारित एक और एल्गोरिथ्म पर चर्चा करेंगे।

समस्या का विवरण

बाइनरी खोज को एक क्रमबद्ध सरणी पर किया जा सकता है। इस दृष्टिकोण में, एक तत्व का सूचकांकxनिर्धारित किया जाता है कि तत्व तत्वों की सूची से संबंधित है या नहीं। यदि सरणी अनसोल्ड है, तो स्थिति को निर्धारित करने के लिए रैखिक खोज का उपयोग किया जाता है।

उपाय

इस एल्गोरिथ्म में, हम यह जानना चाहते हैं कि क्या तत्व है x किसी सरणी में संग्रहीत संख्याओं के समूह के अंतर्गत आता है numbers[]। कहाँ पेl तथा r एक उप-सरणी के बाएं और दाएं सूचकांक का प्रतिनिधित्व करते हैं जिसमें खोज ऑपरेशन किया जाना चाहिए।

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

विश्लेषण

रेखीय खोज में चलता है O(n)समय। जबकि द्विआधारी खोज में परिणाम उत्पन्न करता हैO(log n) समय

लश्कर T(n) एक सरणी में सबसे खराब स्थिति में तुलना की संख्या हो n तत्वों।

इसलिये,

$$ T (n) = \ start {केस} 0 और if \: n = 1 \\ T (\ frac {n} {2}) + 1 और अन्यथा \ केस {केस} $ $

इस पुनरावृत्ति संबंध का उपयोग करते हुए $ T (n) = log \: n $।

इसलिए, द्विआधारी खोज $ O (log \: n) $ समय का उपयोग करता है।

उदाहरण

इस उदाहरण में, हम तत्व 63 को खोजने जा रहे हैं।