आप में से उन लोगों के लिए इंटरपोलेशन सर्च से परिचित नहीं है, यह एक क्रमबद्ध सरणी में एक मूल्य की खोज करने का तरीका है जो बाइनरी खोज से संभावित रूप से तेज़ है। आप पहले और अंतिम तत्व को देखते हैं और (मानते हैं कि सरणी की सामग्री समान रूप से वितरित की जाती है) स्थान की भविष्यवाणी करने के लिए रैखिक रूप से इंटरपोलेट करें।तारों पर इंटरपोलेशन खोज
उदाहरण के लिए: हमारे पास सरणी [0] = 0 और सरणी [99] = 99 के साथ लंबाई 100 की एक सरणी है। यदि हम 80 की तलाश में हैं, तो सरणी [80] पर सरणी [80] की कोशिश करने के लिए सहज है, और यदि सरणी समान रूप से वितरित करने के करीब है, तो अपेक्षित रनटाइम log(log(N))
संख्याओं के लिए, चेक करने के लिए स्थान समीकरण द्वारा परिभाषित किया गया है: low + ((toFind - sortedArray[low]) * (high - low + 1))/(sortedArray[high] - sortedArray[low])।
इंटरपोलेशन खोज की अंतर्ज्ञानी प्रकृति को दिखाने के लिए उपयोग किया जाने वाला एक आम उदाहरण है: एक शब्दकोष में 'पीला' शब्द खोजने का प्रयास करें। आप बाइनरी खोज का उपयोग नहीं करेंगे और आधा रास्ते बिंदु पर नहीं जाएंगे। इसके बजाय, आप अपेक्षित स्थान पर जाएंगे।
मनुष्य स्वाभाविक रूप से रैखिक रूप से तारों को अलग कर सकते हैं, लेकिन मैं यह नहीं समझ सकता कि यह कैसे कोड है। हम स्ट्रिंग्स को रैखिक रूप से कैसे विभाजित करते हैं?
सभी के आसपास अच्छे अंक। +1 –
अतिरिक्त जटिलता 2 बहु/div + 5 add/sub है। मैंने इसका परीक्षण किया है और, हाँ, यह बाइनरी खोज से थोड़ा धीमा है (यदि एन हास्यास्पद नहीं है)। लेकिन अगर तुलना गैर-तुच्छ (जैसे तारों के मामले में) है तो यह मूल्यवान हो सकती है। – user108088
@ user108088, जटिलता दूरी की गणना में भी है, जो स्ट्रिंग के मामले में भी गैर-तुच्छ होगी। मेरा संपादन देखें। –