বাইনারি সার্চ জাভাস্ক্রিপ্ট: একটি গাইড

জাভাস্ক্রিপ্টে বাইনারি সার্চ কীভাবে কোড করবেন

সার্চিং অ্যালগরিদম প্রোগ্রামারের জীবন অনেক সহজ করে দেয়। হাজার হাজার আইটেমের মধ্যে নির্দিষ্ট আইটেম খুঁজে বের করা সহজ হয়।

সবচেয়ে জনপ্রিয় সার্চিং অ্যালগরিদম হলো বাইনারি সার্চ। এটি সর্টেড অ্যারেতে খুব দ্রুত আইটেম খুঁজে বের করে। প্রতিবার সার্চ করলে অবশিষ্ট আইটেমের সংখ্যা আধা হয়ে যায়।

এই গাইডে বাইনারি সার্চ কী, কীভাবে কাজ করে, এবং দুটি পদ্ধতিতে (ইটারেটিভ এবং রিকার্সিভ) ইমপ্লিমেন্টেশন দেখাব।

বাইনারি সার্চ কী?

বাইনারি সার্চ একটি কম্পিউটার সায়েন্স অ্যালগরিদম যা একটি সর্টেড অ্যারেতে আইটেম খুঁজে বের করে।

এটি অ্যারের মাঝপথ থেকে শুরু করে এবং মিডল আইটেমটি টার্গেট নম্বরের চেয়ে ছোট, সমান, নাকি বড় কিনা চেক করে।

যদি ছোট হয়, বাম পাশে (ছোট সংখ্যাগুলো) সার্চ করে; যদি বড় হয়, ডান পাশে (বড় সংখ্যাগুলো) সার্চ করে। বাইনারি সার্চ শুধু সর্টেড লিস্টে কাজ করে।

বাইনারি সার্চ লিনিয়ার সার্চের চেয়ে দক্ষ কারণ প্রতিবার সার্চে অবশিষ্ট আইটেম অর্ধেক হয়ে যায়।

বাইনারি সার্চ কীভাবে ব্যবহার করবেন

বাইনারি সার্চ বুঝা সহজ একবার ধারণা হলে। ইমপ্লিমেন্টেশনের আগে স্টেপ-বাই-স্টেপ চলে দেখি। সর্টেড লিস্টে ৯ খুঁজব:

প্রথমে মিডল নম্বর বের করুন: (শুরু + শেষ) / ২। এখানে মিডল = ৮।

৮ টার্গেট ৯-এর সমান নয়। সার্চ চালিয়ে যাব। ৮, ৯-র চেয়ে ছোট, অর্থাৎ টার্গেট ডান পাশে আছে। তাই নতুন Start = Middle (৮)।

আবার মিডল বের করুন (৮ এবং ১০-এর মাঝপথ): মিডল = ৯।

৯ টার্গেট ৯-এর সমান! সার্চ রুকবে। সফলভাবে ৯ খুঁজে পেয়েছি!

জাভাস্ক্রিপ্টে বাইনারি সার্চ ইমপ্লিমেন্টেশন

বাইনারি সার্চ দুটি পদ্ধতিতে ইমপ্লিমেন্ট করা যায়: ইটারেটিভ এবং রিকার্সিভ।

ইটারেটিভ বাইনারি সার্চ

while লুপ ব্যবহার করে আইটেম খুঁজে বের করা।

function binarySearch(array, numberToFind) { let start = 0; let end = array.length - 1; while (start <= end) { let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { start = middle + 1; } else { end = middle - 1; } } return -1; }

start এবং end ভেরিয়েবল সার্চ রেঞ্জ ট্র্যাক করে। while লুপ চলবে যতক্ষণ start <= end। মিডল ক্যালকুলেট করে টার্গেটের সাথে কমপেয়ার করা হয়। পাওয়া গেলে ইনডেক্স রিটার্ন, না পাওয়া গেলে -১ রিটার্ন (বেস কন্ডিশন)।

মেইন প্রোগ্রাম:

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind); if (findNumber !== -1) { console.log(`${toFind} has been found at position ${findNumber}.`); } else { console.log(`${toFind} has not been found.`); }

ফলাফল: 9 has been found at position 3.

রিকার্সিভ বাইনারি সার্চ

রিকার্সিভ বাইনারি সার্চ আরও এলিগ্যান্ট কারণ একই অপারেশন বারবার রিপিট হয়, যা রিকার্সন দিয়ে সুন্দরভাবে এক্সপ্রেস করা যায়।

function binarySearch(array, numberToFind, start, end) { if (start >= end) { return -1; } let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { return binarySearch(array, numberToFind, middle + 1, end); } else { return binarySearch(array, numberToFind, start, middle - 1); } }

এখানে বেস কেস: start >= end হলে -১ রিটার্ন। মিডল ক্যালকুলেট করে কমপেয়ার। ছোট/বড় হলে ফাংশন নিজেকে আবার কল করে (রিকার্সন)।

মেইন প্রোগ্রামে start এবং end পাস করতে হয়:

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1);

ফলাফল: 9 has been found at position 3.। একই অ্যালগরিদম, রিকার্সিভ আপনিই।

উপসংহার

বাইনারি সার্চ লিস্টে আইটেম খুঁজে বের করা সহজ করে দেয়। প্রতিবার সার্চে অবশিষ্ট আইটেম অর্ধেক হয়ে যাওয়ায় এটি লিনিয়ার সার্চের চেয়ে দক্ষ।

এখন আপনি একজন এক্সপার্টের মতো জাভাস্ক্রিপ্টে বাইনারি সার্চ ইমপ্লিমেন্ট করতে পারবেন!