ब्लॉक खोज
बाइनरी खोज की तरह, ब्लॉक खोज भी क्रमबद्ध सरणियों के लिए एक खोज एल्गोरिदम है। मूल विचार रैखिक खोज की तुलना में कम तत्वों की जांच करना है, निश्चित चरणों से आगे कूदकर या सभी तत्वों को खोजने के स्थान पर कुछ तत्वों को छोड़कर।
उदाहरण के लिए
मान लीजिए हमारे पास लंबाई n की एक सरणी arr और आकार m का ब्लॉक (कूदने के लिए) है। फिर हम सूचकांकों arr[0], arr[m], arr[2 * m], ..., arr[k * m] आदि पर खोज करते हैं।
एक बार जब हमें अंतराल arr[k * m] < x < arr[(k+1) * m] मिल जाता है, तो हम इंडेक्स k * m से तत्व x खोजने के लिए रैखिक खोज संक्रिया करते हैं।
इस एल्गोरिदम की समय जटिलता है -
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
