जावास्क्रिप्ट में ब्लॉक खोज को लागू करना

खोज ब्लॉक करें

बाइनरी सर्च की तरह, ब्लॉक सर्च भी सॉर्ट किए गए सरणियों के लिए एक खोज एल्गोरिथ्म है। मूल विचार यह है कि सभी तत्वों को खोजने के स्थान पर निश्चित चरणों से आगे बढ़कर या कुछ तत्वों को छोड़ कर कम तत्वों (रैखिक खोज की तुलना में) की जांच की जाए।

उदाहरण के लिए

मान लीजिए कि हमारे पास लंबाई n की एक सरणी है और आकार m का ब्लॉक (कूदने के लिए) है। फिर हम अनुक्रमणिका arr[0], arr[m], arr[2 * m], ..., arr[k * m] इत्यादि पर खोज करते हैं।

एक बार जब हमें अंतराल arr[k * m]

इस एल्गोरिथम की समय जटिलता है -

O(√n)

उदाहरण

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

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const blockSearch = (arr = [], target) => {
   let { length: len } = arr;
   let step = Math.floor(Math.sqrt(len));
   let blockStart = 0
   let currentStep = step;
   while (arr[Math.min(currentStep, len) - 1] < target) {
      blockStart = currentStep;
      currentStep += step;
      if (blockStart >= len)
         return -1;
   }
   while (arr[blockStart] < target){
      blockStart++;
      if (blockStart == Math.min(currentStep, len))
         return -1;
   }
   if (arr[blockStart] == target)
      return blockStart
   else
      return -1;
};
console.log(blockSearch(arr, target));

आउटपुट

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

10