बाइनरी सर्च

क्रमबद्ध ऐरे में मान ढूँढता है: बीच में देखता है और वह आधा हिस्सा फेंक देता है जिसमें मान नहीं हो सकता। हर तुलना बचे हिस्से को आधा कर देती है।

• सर्वश्रेष्ठ Ω(1)
• औसत Θ(log n)
• सबसे खराब O(log n)
• मेमोरी O(1)

इनका मतलब क्या है?

• क्रमबद्ध: बढ़ते क्रम में। बाइनरी सर्च को इसकी ज़रूरत है; बिना क्रम वाले डेटा पर यह गलत जवाब देता है।
• आधा करना: हर तुलना बचे हिस्से का आधा फेंक देती है, वह आधा जिसमें लक्ष्य नहीं हो सकता।
• log₂ n: n को कितनी बार आधा किया जा सकता है जब तक 1 न बचे। 64 मानों के लिए यह 6 है, यानी अधिकतम 7 तुलनाएं।