इंटरपोलेशन खोज
इंटरपोलेशन खोज एक एल्गोरिदम है जो संख्यात्मक मानों द्वारा क्रमबद्ध सरणी में एक कुंजी की खोज करता है।
उदाहरण के लिए
मान लीजिए, हमारे पास n समान रूप से वितरित मूल्यों की एक क्रमबद्ध सरणी arr[] है, और हमें सरणी में किसी विशेष तत्व target को खोजने के लिए एक फ़ंक्शन लिखना है।
यह स्थिति खोजने के लिए निम्नलिखित संक्रियाएं करता है -
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))कुंजियाँ -
arr[]- वह सरणी जहां तत्वों को खोजा जाना हैx- खोजा जाने वाला तत्वlo-arr[]में शुरुआती सूचकांकhi-arr[]में अंतिम सूचकांक
हमें एक JavaScript फ़ंक्शन लिखना है जो पहले तर्क के रूप में संख्याओं की एक सरणी और दूसरे तर्क के रूप में खोज लक्ष्य लेता है।
फ़ंक्शन को सरणी में लक्ष्य खोजने के लिए इंटरपोलेशन खोज एल्गोरिदम का उपयोग करना चाहिए।
उदाहरण
निम्नलिखित कोड देखें:
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const interpolationSearch = (arr = [], target) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const rangeDelta = arr[right] - arr[left];
const indexDelta = right - left;
const valueDelta = target - arr[left];
if (valueDelta < 0) {
return -1;
}
if (!rangeDelta) {
return arr[left] === target ? left : -1;
}
const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
if (arr[middleIndex] === target) {
return middleIndex;
}
if (arr[middleIndex] < target) {
left = middleIndex + 1;
} else {
right = middleIndex - 1;
}
};
return -1;
};
console.log(interpolationSearch(arr, target));आउटपुट
कंसोल पर निम्नलिखित आउटपुट प्राप्त होगा:
10
