কিভাবে জাভাস্ক্রিপ্টে একটি বাইনারি অনুসন্ধান কোড করবেন
অ্যালগরিদম অনুসন্ধান করা একজন প্রোগ্রামার হিসাবে জীবনকে অনেক সহজ করে তোলে। এটি করা দশ, শত বা হাজার হাজার আইটেমের ডেটা সেটের মধ্যে একটি নির্দিষ্ট আইটেম খুঁজে পাওয়া সহজ করে তোলে।
অনুসন্ধানের সবচেয়ে জনপ্রিয় ফর্মগুলির মধ্যে একটি হল বাইনারি অনুসন্ধান। এই অনুসন্ধানটি দ্রুত একটি অ্যারেতে একটি আইটেম খুঁজে পায়। প্রতিবার অনুসন্ধান একটি আইটেম মাধ্যমে দেখায়, এটি অর্ধেক দ্বারা অনুসন্ধান করা বাকি আইটেম সংখ্যা হ্রাস.
এই নির্দেশিকায়, আমরা বাইনারি অনুসন্ধানগুলি কী এবং সেগুলি কীভাবে কাজ করে সে সম্পর্কে কথা বলতে যাচ্ছি। তারপরে আমরা দুটি ভিন্ন পদ্ধতি ব্যবহার করে একটি বাইনারি অনুসন্ধান বাস্তবায়ন করতে যাব:পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক।
চলুন জাভাস্ক্রিপ্টে একটি বাইনারি সার্চ অ্যালগরিদম তৈরি করি!
একটি বাইনারি অনুসন্ধান কি?
একটি বাইনারি অনুসন্ধান একটি কম্পিউটার বিজ্ঞান অ্যালগরিদম যা একটি সাজানো অ্যারেতে একটি আইটেম অনুসন্ধান করে।
এটি একটি অ্যারের মাঝখানে শুরু হয় এবং মধ্যবর্তী আইটেমটি আপনি যে সংখ্যার জন্য অনুসন্ধান করছেন তার চেয়ে কম, সমান বা বড় কিনা তা পরীক্ষা করে।
সংখ্যাটি ছোট হলে, অ্যালগরিদম অ্যারের বাম অর্ধেক অনুসন্ধান চালিয়ে যেতে জানে, যেখানে ছোট সংখ্যাগুলি রয়েছে; সংখ্যাটি বড় হলে, অ্যালগরিদম অ্যারের ডান অর্ধেক ফোকাস করবে। বাইনারি অনুসন্ধান শুধুমাত্র সাজানো তালিকায় কাজ করে।
বাইনারি অনুসন্ধানগুলি রৈখিক অনুসন্ধানের চেয়ে বেশি কার্যকর। কারণ প্রতিবার সার্চ করা হলে তালিকায় সার্চ করতে বাকি থাকা আইটেমের সংখ্যা অর্ধেক কমে যায়।
81% অংশগ্রহণকারী বলেছেন যে তারা বুটক্যাম্পে যোগদানের পরে তাদের প্রযুক্তিগত কাজের সম্ভাবনা সম্পর্কে আরও আত্মবিশ্বাসী বোধ করেছেন। আজই একটি বুটক্যাম্পের সাথে মিলিত হন৷
৷গড় বুটক্যাম্প গ্র্যাড একটি বুটক্যাম্প শুরু করা থেকে শুরু করে তাদের প্রথম চাকরি খোঁজা পর্যন্ত ক্যারিয়ারের পরিবর্তনে ছয় মাসেরও কম সময় ব্যয় করেছে।
কিভাবে একটি বাইনারি অনুসন্ধান ব্যবহার করবেন
একটি বাইনারি অনুসন্ধান একবার আপনি এটি হ্যাং পেতে বুঝতে সহজ.
আমরা একটি বাইনারি অনুসন্ধান অ্যালগরিদম প্রয়োগ করার আগে, আসুন এক ধাপে ধাপে চলুন। আমরা একটি তালিকায় "9" নম্বরটি খুঁজে বের করতে যাচ্ছি। একটি সাজানো তালিকা দিয়ে শুরু করা যাক:
| 2 | 6 | 8 | 9 | 10 |
প্রথমত, আমাদের মাঝের সংখ্যাটি খুঁজে বের করতে হবে এবং এটি একটি ভেরিয়েবলে বরাদ্দ করতে হবে। এটি প্রথম এবং শেষ সংখ্যার যোগফল গণনা করে এবং এটি দুটি দ্বারা ভাগ করে পাওয়া যায়। আমরা এই পরিবর্তনশীলটিকে "মিডল" বলব:
| শুরু | | মধ্য | | শেষ |
| 2 | 6 | 8 | 9 | 10 |
8 আমাদের মাঝের সংখ্যা। তারপরে, আমরা মধ্যবর্তী সংখ্যাটির সাথে তুলনা করতে পারি যার জন্য আমরা অনুসন্ধান করছি। মাঝামাঝি সংখ্যাটি আমরা যেটির জন্য অনুসন্ধান করছি তার সমান হলে, আমাদের অনুসন্ধান বন্ধ হয়ে যেতে পারে।
এই উদাহরণে, 8 9 এর সমান নয়। আমাদের অনুসন্ধান চলতে থাকে।
এর পরে, আমাদের তুলনা করতে হবে যে মধ্যম সংখ্যাটি 9-এর চেয়ে বেশি। এটা নয়।
এটি আমাদের বলে যে আমরা যে সংখ্যাটির জন্য অনুসন্ধান করছি তা অবশ্যই মধ্যম সংখ্যার পরে হবে। একটি সাজানো তালিকায় 9 হল 8 এর থেকে বড়। আমরা আমাদের প্রারম্ভিক সংখ্যাটি মধ্যম সংখ্যার সমান করতে যাচ্ছি। কারণ আমরা জানি যে আমরা যে সংখ্যাটি খুঁজছি সেটি মধ্যম সংখ্যার আগে আসে না।
আমরা যে সংখ্যাটির জন্য অনুসন্ধান করছি তা যদি ছোট হয় তবে আমরা শেষ সংখ্যাটিকে মধ্যবর্তী সংখ্যার সমান হিসাবে সেট করব। কারণ সংখ্যাটি মধ্যবর্তী সংখ্যার চেয়ে ছোট, আমরা তালিকার নীচের অর্ধেকের দিকে আমাদের অনুসন্ধানকে ফোকাস করতে পারি।
বাইনারি অনুসন্ধান আবার তালিকার উপরের অর্ধেকের পুনরাবৃত্তি করে কারণ 9 8 এর চেয়ে বড়:
| | | শুরু করুন | মধ্য | শেষ |
| 2 | 6 | 8 | 9 | 10 |
আমরা আবার মধ্যম সংখ্যা খুঁজে. এটি হল 9। আমরা যে সংখ্যাটির জন্য অনুসন্ধান করছি তার সাথে আমরা 9কে তুলনা করতে পারি। 9 হল সেই সংখ্যার সমান যার জন্য আমরা অনুসন্ধান করছি।
এর মানে আমাদের অনুসন্ধান বন্ধ হতে পারে। আমরা সফলভাবে আমাদের তালিকায় 9 নম্বরটি খুঁজে পেয়েছি!
জাভাস্ক্রিপ্টে একটি বাইনারি অনুসন্ধান কীভাবে প্রয়োগ করবেন
বাইনারি অনুসন্ধানগুলি একটি পুনরাবৃত্তিমূলক বা পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে প্রয়োগ করা যেতে পারে।
পুনরাবৃত্ত বাইনারি অনুসন্ধান
একটি পুনরাবৃত্তিমূলক বাইনারি অনুসন্ধান একটি তালিকায় একটি আইটেম খুঁজে পেতে একটি সময় লুপ ব্যবহার করে। আইটেমটি তালিকায় না পাওয়া পর্যন্ত বা তালিকাটি অনুসন্ধান না করা পর্যন্ত এই লুপটি কার্যকর হবে।
আসুন একটি ফাংশন লিখে শুরু করি যা আমাদের বাইনারি অনুসন্ধান সম্পাদন করে:
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;
}
আমরা দুটি ভেরিয়েবল সংজ্ঞায়িত করে শুরু করি:শুরু এবং শেষ। এগুলি আমাদের অনুসন্ধানের সাথে কাজ করছে সর্বোচ্চ এবং সর্বনিম্ন মানগুলির ট্র্যাক রাখে৷ আমরা একটি while লুপ ব্যবহার করি যা স্টার্ট নাম্বার শেষ সংখ্যার চেয়ে বড় না হওয়া পর্যন্ত চলে। এই লুপ তালিকায় শুরু এবং শেষের মধ্যবর্তী সংখ্যা গণনা করে।
যে সংখ্যাটির জন্য আমরা অনুসন্ধান করছি সেটি মধ্যম সংখ্যার সমান হলে, মধ্যম সংখ্যাটি আমাদের মূল প্রোগ্রামে ফিরে আসবে। সংখ্যাটি ছোট হলে, শুরুর মানটি মধ্যম সংখ্যা প্লাস ওয়ানের সমান হতে সেট করা হয়। এই তুলনা একটি if স্টেটমেন্ট ব্যবহার করে সঞ্চালিত হয়।
অন্যথায়, শেষ সংখ্যাটি মধ্যবর্তী সংখ্যা বিয়োগ একের সমান হবে। while লুপ চালানোর পর যদি আমাদের নম্বর না পাওয়া যায়, -1 ফেরত দেওয়া হয়। এটাকে আমরা বেস কন্ডিশন বলি। আমাদের মূল প্রোগ্রামে, আমরা পরীক্ষা করব যে ফেরত নম্বরটি -1 এর সমান কিনা। যদি তা হয়, তাহলে এর মানে আমাদের নম্বর পাওয়া যায়নি।
আমাদের ফাংশন এখনও কাজ করে না। আমাদের একটি প্রধান প্রোগ্রাম লিখতে হবে যা এটিকে বলে:
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.`);
}
আমরা সংখ্যার একটি তালিকা সংজ্ঞায়িত করেছি যার মাধ্যমে অনুসন্ধান করতে হবে এবং যে নম্বরটি আমরা আমাদের তালিকায় খুঁজে পেতে চাই। এর পরে, আমরা বাইনারি সার্চ ফাংশনকে কল করেছি। এটি আমাদের অনুসন্ধান সম্পাদন করবে। অনুসন্ধানটি হয় -1 বা যে আইটেমটির জন্য আমরা অনুসন্ধান করছি তার অবস্থান ফিরে আসবে।
-1 বোঝায় যে একটি আইটেম পাওয়া যায়নি। যদি একটি আইটেম পাওয়া না যায়, আমাদের else এর বিষয়বস্তু বিবৃতি কার্যকর করা হয়। অন্যথায়, if এর বিষয়বস্তু বিবৃতি চালানো হয়.
আসুন আমাদের কোড রান করি:
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);
}
}
এই কোডটি আমাদের প্রথম অনুসন্ধানের মতো একই তুলনা করে। এটি পরীক্ষা করে যে মাঝামাঝি সংখ্যাটি আমরা যে সংখ্যাটির জন্য অনুসন্ধান করছি তার সমান, এর চেয়ে বড় বা কম কিনা।
আমাদের ফাংশনের শুরুতে, আমরা একটি if স্টেটমেন্ট ব্যবহার করেছি যাতে স্টার্ট নম্বরটি শেষ সংখ্যার চেয়ে বড় কিনা। যদি তা হয়, তাহলে এর মানে আমাদের নির্দিষ্ট করা তালিকায় আমাদের আইটেম পাওয়া যায়নি। যদি এটি হয় তবে আমরা মূল প্রোগ্রামে -1 ফিরে আসি।
যদি আমরা যে নম্বরটি খুঁজছি সেটি মধ্যম সংখ্যার মতোই হয়, তবে মধ্যম সংখ্যাটি মূল প্রোগ্রামে ফিরে আসে। আমরা যে সংখ্যাটি খুঁজছি সেটি মধ্যবর্তী সংখ্যার চেয়ে বড় বা কম হলে, আমাদের বাইনারি সার্চ ফাংশনটি আবার চালানো হবে। আমাদের আইটেম পাওয়া না হওয়া পর্যন্ত এটি চলতে থাকে।
এই ফাংশনটি চালানোর জন্য, আমাদের মূল প্রোগ্রামে একটি পরিবর্তন করতে হবে:
let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1); …
আমাদের দুটি অতিরিক্ত পরামিতি পাস করতে হবে:"শুরু" এবং "শেষ" এর মান। "শুরু" এর মান 0 এর সমান। "শেষ" এর মান তালিকার দৈর্ঘ্য বিয়োগ একের সমান।
আসুন আমাদের কোড চালাই এবং দেখুন কি হয়:
9 has been found at position 3.
আমাদের বাইনারি অনুসন্ধান সফল হয়েছে! এটি পুনরাবৃত্তিমূলক পদ্ধতির মতো একই অন্তর্নিহিত অ্যালগরিদম ব্যবহার করে। পার্থক্য হল বাইনারি অনুসন্ধান একটি ফাংশন ব্যবহার করে সঞ্চালিত হয় যা আইটেমটি খুঁজে না পাওয়া পর্যন্ত বা তালিকাটি সম্পূর্ণরূপে অনুসন্ধান না হওয়া পর্যন্ত, যেটি প্রথমে আসে।
উপসংহার
বাইনারি অনুসন্ধানগুলি একটি তালিকায় একটি আইটেম খুঁজে পাওয়া সহজ করে তোলে। প্রতিবার একটি অনুসন্ধান চালানো হয়, একটি তালিকায় অনুসন্ধান করতে বাকি আইটেম সংখ্যা অর্ধেক দ্বারা হ্রাস করা হয়. এটি একটি লিনিয়ার অনুসন্ধানের চেয়ে একটি বাইনারি অনুসন্ধানকে আরও দক্ষ করে তোলে।
এখন আপনি একজন বিশেষজ্ঞের মতো জাভাস্ক্রিপ্টে বাইনারি অনুসন্ধান বাস্তবায়নের জন্য প্রস্তুত!
