इंटरपोलेशन खोज में मध्य कंप्यूटिंग?

Question

मैं जानना चाहता हूँ कि अंतर्वेशन खोजें की बाइनरी खोजें एक संशोधन जहां द्विआधारी खोज में इनपुट

mid = (low + high)/2 

और अंतर्वेशन खोज मध्य है कंप्यूटिंग द्वारा प्रत्येक चरण में दो बराबर हिस्सों में बांटा गया है है आया के रूप में

mid = low + (key - arr[low]) * ((high - low)/(arr[high] - arr[low])) 

अभिकलन अब मैं प्रक्षेप खोज में mid की गणना के इस सूत्र को समझना होगा।

रेफरी: https://en.wikipedia.org/wiki/Interpolation_search#Sample_implementation

Answer 1

आप एक समारोह f कि सूचकांक पर कार्य करता है और कोई मान है, जो एक लय है (क्योंकि सरणी सॉर्ट हो जाता है) के रूप में सरणी arr के बारे में सोच सकते हैं। तो आपके पास अपना प्रारंभिक डेटा f(low) = m और f(high) = M है। अब आप एक सीधी रेखा के साथ अपने फ़ंक्शन f को इंटरपोलेट कर सकते हैं, जो ऐसा करने के लिए काफी उचित है क्योंकि आपका f मोनोटोन है और आपके पास केवल 2 अंक हैं। तो आपका इंटरपोलेशन लाइन (रैखिक फ़ंक्शन) होना चाहिए जो फेंक पॉइंट (low, m) और (high, M) पास करे। यह समीकरण

(y - f(low))/(f(high) - f(low)) = (x - low)/(high - low) 

तो y यहाँ खोज अंतरिक्ष के तत्व है और x (एक्स सरणी के सूचकांक है) डोमेन से है है। इसलिए यदि आपके समारोह f ही होगा के रूप में यह प्रक्षेप के सूचकांक है, तो अपने key होगा:

x = low + (high - low)*(key - f(low))/(f(high) - f(low)) 

तो, यह सोचते हैं कि अपने कार्य f यह प्रक्षेप के करीब है, तो आप सिर्फ मूल्य fx पर जांच होनी चाहिए यह देखने के लिए कि क्या यह लक्ष्य है। अन्यथा आप बस अपने इंटरपोलेशन अंतराल को कम करें।

Answer 2

एक extention जवाब देने के लिए @JustAnotherCurious

उसके द्वारा perposed समीकरण पर Interpolation Formula (एक लाइन के क्षेत्रों में काम)

अब आधारित था, समारोह के रूप में लगता है f() जो एक सूचकांक लेता है और y धुरी मूल्य,

लौटाता है

y1 = f(low) 
y2 = f(high) 
x1 = low 
x2 = high 

(y - f(low)) = [(f(high) - f(low))/(high - low)] * (x - low); 

OR 

x = low + [(high - low) * (y - f(low))]/(f(high) - f(low)) 

here: y = key 
we are looking for position(value) of x.