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

रैखिक खोज

रैखिक खोज अनुक्रमिक रूप से सूची में प्रत्येक तत्व की जांच करता है जब तक कि यह लक्ष्य नहीं पाता है या अंत तक पहुंच जाता है। तुलना की उम्मीद की गई संख्या इस बात पर निर्भर करती है कि लक्ष्य मौजूद है और सूची में इसकी स्थिति क्या है।

यदि सूची में n तत्व और लक्ष्य किसी भी स्थिति में होने की संभावना समान है, तो तुलना की अपेक्षित संख्या है:

]Expected तुलना = (n + 1) / 2

ऐसा इसलिए है क्योंकि, औसतन, खोज सूची के माध्यम से लक्ष्य आधे रास्ते को ढूंढेगा।

द्विआधारी खोज

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

सबसे अच्छे मामले में, लक्ष्य मध्य में है, केवल एक तुलना की आवश्यकता होती है। सबसे खराब मामले में, यह लगभग log]2]]n] तुलना लेता है।

लक्ष्य को मानने के लिए किसी भी स्थिति में समान रूप से होने की संभावना है, तुलना की अपेक्षित संख्या मोटे तौर पर होती है:

]Expected तुलना ≈ log2]n]]]

तुलना सारांश

  • रैखिक खोज की उम्मीद की तुलना की गिनती (n + 1) / 2.
  • बाइनरी खोज में लगभग लॉग की अनुमानित तुलना की गणना है 2 n.
  • बाइनरी खोज में आम तौर पर बड़ी सूचियों के लिए कम तुलना की आवश्यकता होती है।
  • रैखिक खोज छोटे या बिना किसी श्रेणी की सूचियों के लिए बेहतर हो सकता है।