बायनरी सर्च असलेले सॉर्ट केलेले अॅरे हे एक अत्यंत अकार्यक्षम उपाय आहे जेव्हा समाविष्ट करणे आणि हटविणे ऑपरेशन्स पुनर्प्राप्तीसह इंटरलेव्ह केले जातात. याव्यतिरिक्त, क्रमवारी लावलेल्या अॅरे मेमरी वापरात अडथळा आणू शकतात, विशेषतः जेव्हा अॅरेमध्ये घटक वारंवार घातले जातात. बायनरी शोध क्रमवारी लावलेल्या अॅरेसाठी रेषेच्या शोधापेक्षा वेगवान आहे, जर अॅरे लहान असेल तर, जरी अॅरेला आधीपासून क्रमवारी लावण्याची आवश्यकता असेल. बायनरी शोध हे सामान्यतः शोध घेण्यासाठी अधिक कार्यक्षम असते कारण बायनरी शोध झाडे बहुधा अपूर्णपणे संतुलित असतील, परिणामी बायनरी शोधपेक्षा किंचित वाईट कामगिरी होईल. एक हॅश फंक्शन वापरून रेकॉर्ड्सची की मॅप करणारी डेटा स्ट्रक्चर, सामान्यतः रेकॉर्ड्सच्या क्रमवारी लावलेल्या अॅरेवर बायनरी शोधपेक्षा वेगवान असते.
बायनरी सर्च आणि इतर सर्च स्कीम कशा आहेत?
Context:बायनरी शोध असलेले सॉर्ट केलेले अॅरे हे एक अत्यंत अकार्यक्षम उपाय आहे जेव्हा समाविष्ट करणे आणि हटविणे ऑपरेशन्स पुनर्प्राप्तीसह इंटरलेव्ह केले जातात,  ओ (एन) वेळ अशा प्रत्येक ऑपरेशनसाठी. याव्यतिरिक्त, क्रमवारी लावलेल्या अॅरे मेमरी वापरात अडथळा आणू शकतात, विशेषतः जेव्हा अॅरेमध्ये घटक वारंवार घातले जातात. इतर डेटा संरचना आहेत ज्यात अधिक कार्यक्षम समाविष्ट करणे आणि हटविणे समर्थित आहे. बायनरी शोध अचूक जुळणी आणि सेट सदस्यता (लक्ष्य मूल्य मूल्यांच्या संग्रहात आहे की नाही हे निर्धारित करण्यासाठी) करण्यासाठी वापरला जाऊ शकतो. अशी डेटा संरचना आहेत जी वेगवान अचूक जुळणी आणि सेट सदस्यता समर्थित करतात. तथापि, इतर बर्याच शोध योजनांप्रमाणे, बायनरी शोध कार्यक्षम अंदाजे जुळवणीसाठी वापरला जाऊ शकतो, सामान्यतः अशा जुळवणींमध्ये O ((लॉग एन) वेळ मूल्यांचे प्रकार किंवा संरचनेकडे दुर्लक्ष करून. याव्यतिरिक्त, काही ऑपरेशन्स आहेत, जसे की सर्वात लहान आणि सर्वात मोठा घटक शोधणे, जे क्रमवारी लावलेल्या अॅरेवर कार्यक्षमतेने केले जाऊ शकते.  रेषेचा शोध:  रेषेचा शोध हा एक सोपा शोध अल्गोरिदम आहे जो लक्ष्य मूल्य शोधण्यापर्यंत प्रत्येक रेकॉर्ड तपासतो. रेषेचा शोध लिंक्ड लिस्टवर करता येतो, ज्यामुळे अॅरेपेक्षा वेगवान समाविष्ट करणे आणि हटविणे शक्य होते. बायनरी शोध क्रमवारी लावलेल्या अॅरेसाठी रेषेच्या शोधापेक्षा वेगवान आहे, जर अॅरे लहान असेल तर, जरी अॅरेला आधीपासून क्रमवारी लावण्याची आवश्यकता असेल. क्विक सॉर्ट आणि मर्ज सॉर्ट सारख्या तुलनात्मक घटकांवर आधारित सर्व सॉर्टिंग अल्गोरिदमसाठी किमान आवश्यक आहे O ((nlog n) सर्वात वाईट परिस्थितीत तुलना. रेषीय शोधाच्या विपरीत, बायनरी शोधाचा उपयोग कार्यक्षम अंदाजे जुळण्यासाठी केला जाऊ शकतो. अशा ऑपरेशन्स आहेत जसे की सर्वात लहान आणि सर्वात मोठा घटक शोधणे जे क्रमवारी लावलेल्या अॅरेवर कार्यक्षमतेने केले जाऊ शकते परंतु क्रमवारी लावलेल्या अॅरेवर नाही.  झाडे:  बायनरी सर्च ट्री बायनरी सर्च प्रमाणेच अल्गोरिदम वापरून सर्च केले जाते. बायनरी सर्च ट्री ही बायनरी ट्री डेटा स्ट्रक्चर आहे जी बायनरी सर्चच्या तत्त्वावर आधारित कार्य करते. झाडाच्या नोंदी क्रमवारीत क्रमवारीत आहेत, आणि झाडामधील प्रत्येक रेकॉर्ड बायनरी शोध सारख्या अल्गोरिदमचा वापर करून शोधला जाऊ शकतो, सरासरी लॉगरिदमिक वेळ घेत आहे. बायनरी सर्च ट्रीमध्ये समाविष्ट करणे आणि हटविणे यासाठी सरासरी लॉगरिदमिक वेळ लागतो. हे क्रमवारी लावलेल्या अॅरेच्या रेषेच्या वेळेच्या समाविष्टीकरण आणि हटविण्यापेक्षा वेगवान असू शकते आणि बायनरी झाडे श्रेणी आणि अंदाजे क्वेरींसह क्रमवारी लावलेल्या अॅरेवर सर्व ऑपरेशन्स शक्य करण्याची क्षमता राखून ठेवतात.  तथापि, बायनरी शोध सामान्यतः शोध घेण्यासाठी अधिक कार्यक्षम असतो कारण बायनरी शोध झाडे बहुधा अपूर्णपणे संतुलित असतील, परिणामी बायनरी शोधपेक्षा किंचित वाईट कामगिरी होईल. हे अगदी संतुलित बायनरी शोध वृक्षांवर लागू होते, बायनरी शोध वृक्ष जे त्यांच्या स्वतः च्या नोड्सचे संतुलन करतात, कारण ते क्वचितच शक्य तितक्या कमी पातळीसह झाड तयार करतात. संतुलित बायनरी शोध वृक्षांना वगळता, झाड दोन मुलांसह काही अंतर्गत नोड्ससह गंभीरपणे असंतुलित असू शकते, परिणामी सरासरी आणि सर्वात वाईट परिस्थिती शोध वेळ जवळ येत आहे n तुलना. [e] बायनरी शोध झाडे क्रमवारी लावलेल्या अॅरेपेक्षा अधिक जागा घेतात.  बायनरी सर्च ट्री हार्ड डिस्कमध्ये साठवलेल्या बाह्य मेमरीमध्ये जलद शोध घेण्यास उपयुक्त आहेत, कारण बायनरी सर्च ट्री फायली सिस्टीममध्ये कार्यक्षमतेने संरचित केले जाऊ शकतात. बी-ट्री ही झाडाच्या संघटनेची पद्धत सामान्य करते. डेटाबेस आणि फाइल सिस्टीम यासारख्या दीर्घकालीन संचयनासाठी बी-ट्रीचा वापर केला जातो.  हॅशिंग: असोसिएटिव्ह अॅरेची अंमलबजावणी करण्यासाठी, हॅश टेबल, एक डेटा स्ट्रक्चर जे हॅश फंक्शनचा वापर करून रेकॉर्ड्सच्या की मॅप करते, सामान्यतः रेकॉर्ड्सच्या सॉर्ट केलेल्या अॅरेवर बायनरी शोधपेक्षा वेगवान असतात. बहुतेक हॅश टेबल अंमलबजावणीसाठी सरासरी केवळ अॅमॉर्टिज्ड कॉन्स्टंट वेळ आवश्यक असतो. तथापि, पुढील-सर्वात लहान, पुढील-सर्वात मोठा आणि सर्वात जवळचा की गणना करण्यासारख्या अंदाजे जुळण्यांसाठी हॅशिंग उपयुक्त नाही, कारण अयशस्वी शोधावर दिलेली एकमेव माहिती अशी आहे की लक्ष्य कोणत्याही रेकॉर्डमध्ये उपस्थित नाही. बायनरी शोध अशा जुळण्यांसाठी आदर्श आहे, त्यांना लॉगरिदमिक वेळेत करते. बायनरी शोध अंदाजे जुळण्यांना देखील समर्थन देते. काही ऑपरेशन्स, जसे की सर्वात लहान आणि सर्वात मोठा घटक शोधणे, क्रमवारी लावलेल्या अॅरेवर कार्यक्षमतेने केले जाऊ शकते परंतु हॅश टेबलवर नाही.  सदस्यता अल्गोरिदम सेट करा: शोधाशी संबंधित समस्या म्हणजे सेट सदस्यता. बायनरी सर्च सारखे लुकअप करणारे कोणतेही अल्गोरिदम सेट मेंबरशिपसाठी वापरले जाऊ शकते. इतरही अल्गोरिदम आहेत जे संच सदस्यत्वासाठी अधिक उपयुक्त आहेत. बिट अॅरे हा सर्वात सोपा प्रकार आहे, जेव्हा कीची श्रेणी मर्यादित असते तेव्हा ते उपयुक्त असते. हे बिट्सचे संकलन संक्षिप्तपणे संग्रहित करते, प्रत्येक बिट कीच्या श्रेणीमध्ये एकमेव की दर्शविते. बिट अॅरे खूप जलद आहेत, फक्त आवश्यक O(1) वेळ. ज्युडी1 प्रकारची ज्युडी अॅरे 64-बिट की कार्यक्षमतेने हाताळते.  अंदाजे परिणामांसाठी, ब्लूम फिल्टर, हॅशिंगवर आधारित आणखी एक संभाव्य डेटा संरचना, बिट अॅरे आणि एकाधिक हॅश फंक्शन्स वापरुन की एन्कोड करून कीचा एक संच संग्रहित करते. ब्लूम फिल्टर बहुतांश प्रकरणांमध्ये बिट अॅरेपेक्षा जास्त जागा-कार्यक्षम असतात आणि जास्त धीमे नसतात: k हॅश फंक्शन्स, सदस्यत्व क्वेरी केवळ आवश्यक आहे ठीक आहे. तथापि, ब्लूम फिल्टर्स खोट्या सकारात्मकतेमुळे ग्रस्त आहेत.  इतर डेटा संरचना: अशी डेटा संरचना आहेत जी काही प्रकरणांमध्ये बायनरी शोधामध्ये सुधारणा करू शकतात शोध आणि इतर ऑपरेशन्स दोन्ही क्रमवारी लावलेल्या अॅरेसाठी उपलब्ध आहेत. उदाहरणार्थ, शोध, अंदाजे जुळणी आणि क्रमवारी लावलेल्या अॅरेसाठी उपलब्ध ऑपरेशन्स व्हॅन एम्डे बोस झाडे, फ्यूजन झाडे, ट्राय आणि बिट अॅरे यासारख्या विशेष डेटा स्ट्रक्चर्सवर बायनरी शोधपेक्षा अधिक कार्यक्षमतेने केले जाऊ शकतात. या विशेष डेटा संरचना सहसा फक्त वेगवान असतात कारण त्या विशिष्ट गुणधर्मांसह कीच्या गुणधर्मांचा फायदा घेतात (सामान्यतः लहान पूर्णांक असलेली की), आणि अशा प्रकारे त्या गुणधर्माची कमतरता असलेल्या कीसाठी वेळ किंवा जागा घेतात. जोपर्यंत की ऑर्डर करता येतील, तोपर्यंत ही ऑपरेशन्स नेहमी कमीत कमी कार्यक्षमतेने सॉर्ट केलेल्या अॅरेवर केली जाऊ शकतात. ज्युडी अॅरेसारख्या काही रचना, कार्यक्षमता आणि अंदाजे जुळणी करण्याची क्षमता राखून ठेवून हे कमी करण्यासाठी पध्दतींचे संयोजन वापरतात.