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