इंटरपोलेशन सर्च

फ़ोन बुक में "Taylor" खोजते समय आप उसे बीच में नहीं खोलते: आप उसे पीछे की ओर खोलते हैं, क्योंकि T वर्णमाला में काफ़ी बाद में आता है। इंटरपोलेशन सर्च संख्याओं के साथ यही करता है। यह लक्ष्य के आकार से अनुमान लगाता है कि वह कहाँ होना चाहिए, और बराबर फैले डेटा पर यह अनुमान कमाल का सटीक होता है।

सॉर्ट किए गए बार की एक पंक्ति, पहले से आख़िरी बार तक जाती एक रेखा, और वहाँ रखी जाँच जहाँ लक्ष्य की ऊँचाई उस रेखा से मिलती है
सॉर्ट किए गए बार की एक पंक्ति, पहले से आख़िरी बार तक जाती एक रेखा, और वहाँ रखी जाँच जहाँ लक्ष्य की ऊँचाई उस रेखा से मिलती है

मूल विचार

बाइनरी सर्च चाहे कुछ भी खोज रहा हो, हमेशा बीच में जाँचता है। इंटरपोलेशन सर्च मानों का इस्तेमाल करता है। अगर सूची का बचा हुआ हिस्सा 10 से 100 तक है और लक्ष्य 70 है, तो लक्ष्य पहले मान से आख़िरी मान तक के रास्ते के दो-तिहाई पर है, इसलिए यह उस हिस्से में दो-तिहाई आगे जाँचता है। फ़ॉर्मूले में, जाँच का स्थान lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo) है। जाँच के बाद यह बिल्कुल बाइनरी सर्च की तरह सही तरफ़ का हिस्सा रखता है, और फिर से अनुमान लगाता है।

दो उदाहरण

10, 20, 30, 40, 50, 60, 70, 80, 90, 100 में 70 खोजने पर यह सीधे स्थान 7 जाँचता है: 1 जाँच में मिल जाता है, जबकि बाइनरी सर्च को 4 चाहिए। अब 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 लें और 9 खोजें। 999 की वजह से हर अनुमान शुरुआत के पास पड़ता है: सर्च स्थान 1, 2, 3 वगैरह को एक-एक करके जाँचता है, और 9 जाँचें लगती हैं, जबकि बाइनरी सर्च को 3 चाहिए।

यह कितना तेज़ है

जब मान बराबर फैले हों, या किसी एकसमान डिस्ट्रिब्यूशन से रैंडम चुने गए हों, तो हर जाँच बचे हुए हिस्से को लगभग n से घटाकर लगभग √n कर देती है। इससे औसतन लगभग log₂(log₂ n) जाँचें लगती हैं: एक अरब मानों के लिए भी लगभग 5, जबकि बाइनरी सर्च को 30 चाहिए। जब मान बहुत असमान फैले हों, तो एक जाँच शायद सिर्फ़ एक मान हटाए, और सबसे ख़राब स्थिति में n जाँचें लगती हैं, यानी लीनियर सर्च जितना बुरा। हर जाँच में एक भाग भी लगता है, इसलिए व्यवहार में यह मुख्य रूप से तब फ़ायदेमंद है जब जाँच महँगी हो, जैसे डिस्क से पढ़ना।

इतिहास और रूप

W. W. Peterson ने 1957 में रैंडम-एक्सेस स्टोरेज पर रिकॉर्ड खोजने के लिए इंटरपोलेशन सर्च का वर्णन किया। बराबर फैली कुंजियों के लिए इसका log log n औसत 1978 में Perl, Itai और Avni ने साबित किया। व्यावहारिक संस्करण ख़राब डेटा से बचने के लिए बीच-बीच में बाइनरी चरण मिलाते हैं, जैसे इंटरपोलेशन-सीक्वेंशियल सर्च या इंटरपोलेशन-बाइनरी सर्च, ताकि सबसे ख़राब स्थिति log n के पास रहे।

आज़माकर देखें

ऐप खोलें, ‘खोजें’ में कोई मान चुनें, और ‘आगे’ दबाएँ। हर जाँच बताती है कि लक्ष्य दोनों सिरों के मानों के बीच कितनी दूर है और वह किस स्थान की ओर इशारा करता है। ‘फैलाव’ को ‘बराबर’ पर करें तो ज़्यादातर सर्च एक जाँच में ख़त्म हो जाते हैं; ‘झुका हुआ’ पर करें तो जाँचें सूची की शुरुआत में धीरे-धीरे रेंगती हैं। आख़िरी टाइल दिखाती है कि उसी मान के लिए बाइनरी सर्च को कितने चरण चाहिए।

अक्सर पूछे जाने वाले प्रश्न

इंटरपोलेशन सर्च की टाइम कॉम्प्लेक्सिटी क्या है?

बराबर फैले मानों पर औसतन O(log log n), और सबसे ख़राब स्थिति में O(n)। इसे O(1) अतिरिक्त मेमोरी और सॉर्ट की हुई सूची चाहिए।

इंटरपोलेशन सर्च और बाइनरी सर्च में क्या अंतर है?

बाइनरी सर्च हमेशा बचे हुए हिस्से के बीच में जाँचता है। इंटरपोलेशन सर्च दोनों सिरों के मानों के आधार पर वहाँ जाँचता है जहाँ लक्ष्य होना चाहिए। बराबर फैले मानों पर यह कहीं बेहतर है और झुके हुए मानों पर कहीं बुरा हो सकता है।

किस तरह का डेटा इंटरपोलेशन सर्च के लिए सही है?

सॉर्ट की हुई संख्यात्मक कुंजियाँ जो काफ़ी बराबर फैली हों: कम खाली जगहों वाली क्रमिक ID, नियमित घटनाओं के टाइमस्टैम्प, या हैश की गई कुंजियाँ। यह ऐसे डेटा के लिए सही है जहाँ जाँच महँगी हो और थोड़ा हिसाब सस्ता।

ऐप में अलग-अलग फैलाव क्यों हैं?

क्योंकि फैलाव तय करता है कि अनुमान कितने अच्छे होंगे। बराबर मान इंटरपोलेशन सर्च को लगभग जादुई दिखाते हैं, और झुके हुए मान उसकी कमज़ोरी दिखाते हैं। इनकी तुलना बाइनरी सर्च की गिनती से करना यह समझने का सबसे साफ़ तरीका है कि कब कौन-सा इस्तेमाल करें।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

इंटरपोलेशन सर्च आज़माएँ