অনুসন্ধান ব্লক করুন
বাইনারি অনুসন্ধানের মতো, ব্লক অনুসন্ধানও সাজানো অ্যারেগুলির জন্য একটি অনুসন্ধান অ্যালগরিদম। মূল ধারণা হল নির্দিষ্ট ধাপে এগিয়ে গিয়ে বা সমস্ত উপাদান অনুসন্ধানের জায়গায় কিছু উপাদান বাদ দিয়ে কম উপাদান (রৈখিক অনুসন্ধানের চেয়ে) পরীক্ষা করা।
উদাহরণস্বরূপ
ধরুন আমাদের দৈর্ঘ্য 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
