जावास्क्रिप्ट में इंटरपोलेशन सर्च

<घंटा/>

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

इंटरपोलेशन खोज एक सरणी में एक कुंजी की खोज के लिए एक एल्गोरिदम है जिसे कुंजी (कुंजी मान) को असाइन किए गए संख्यात्मक मानों द्वारा क्रमबद्ध किया गया है।

उदाहरण के लिए

मान लीजिए, हमारे पास n समान रूप से वितरित मानों की एक क्रमबद्ध सरणी है arr[], और हमें सरणी में किसी विशेष तत्व लक्ष्य की खोज के लिए एक फ़ंक्शन लिखने की आवश्यकता है।

यह स्थिति खोजने के लिए निम्नलिखित ऑपरेशन करता है -

// सूत्र का विचार पॉज़ का उच्च मान लौटाना है

// जब खोजा जाने वाला तत्व गिरफ्तारी के करीब है [हाय]। और

// छोटा मान जब गिरफ्तारी के करीब हो [lo]

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))

कुंजी −

arr[] - ऐरे जहां तत्वों की खोज की जानी चाहिए
x - खोजा जाने वाला तत्व
lo - गिरफ्तारी में अनुक्रमणिका शुरू करना []
hi - अनुक्रमणिका को गिरफ्तारी में समाप्त करना[]

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखने की आवश्यकता है जो पहले तर्क के रूप में संख्याओं की एक सरणी और दूसरे तर्क के रूप में एक खोज लक्ष्य लेता है।

सरणी में लक्ष्य को खोजने के लिए फ़ंक्शन को इंटरपोलेशन खोज एल्गोरिदम का उपयोग करना चाहिए।

उदाहरण

निम्नलिखित कोड है -

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));

आउटपुट

कंसोल पर आउटपुट निम्न है -