একটি অ্যারেতে বাইনারি সার্চ বাস্তবায়ন করা

সুবিন্যস্ত অ্যারেতে বাইনারি সার্চের প্রয়োগ দেখা যাক। ঠিক, জাভাস্ক্রিপ্টের নিজস্ব মেথড আছে যা অ্যারের কোন উপাদান এবং এটির অবস্থান খুঁজে বের করতে পারে (অনেক প্রোগ্রামিং ভাষাতেই এমনটি করা যায়), কিন্তু আমরা এই বিষয় সম্পর্কে পরিপূর্ণ ধারনা লাভের জন্য এটি নিজেরা তৈরি করতে চাই। এখানে সুবিন্যস্তভাবে একটি জাভাস্ক্রিপ্টের প্রথম 2 5 টি মৌলিক সংখ্যার অ্যারে রয়েছেঃ

ধরি, আমরা জানতে চাই 67 সংখ্যাটি মৌলিক সংখ্যা কিনা। যদি 67 অ্যারেতে থাকে, তাহলে এটি মৌলিক সংখ্যা হবে।

আমরা এটিও জানতে চেতে পারি যে, 67 থেকে ছোট কতগুলো মৌলিক সংখ্যা রয়েছে। যদি আমরা অ্যারেতে 67 এর অবস্থান খুঁজে পাই, তাহলে এটি ব্যবহার করে আমরা ছোট সংখ্যাগুলো খুঁজে বের করতে পারি।

অ্যারেতে কোন উপাদানের অবস্থানকে ইন্ডেক্স বলা হয়। অ্যারের ইন্ডেক্স 0 থেকে শুরু হয়ে বৃদ্ধি পায়। যদি কোন উপাদান 0 ইন্ডেক্সে থাকে, তাহলে এটি অ্যারের প্রথম উপাদান। যদি একটি উপাদান 3 ইন্ডেক্সে থাকে, তাহলে বোঝা যায় যে অ্যারেতে ব্যাঘাত এটির আগে আরও 3 টি উপাদান রয়েছে।

নিচের উদাহরণে, আমরা বাম থেকে ডানদিকে অ্যারেতে একটি করে মৌলিক সংখ্যাগুলো পড়তে পারি, যতক্ষণ পর্যন্ত না আমরা 67 (গোলাপি বক্সে) খুঁজে পাই এবং দেখি যে এটির ইন্ডেক্স হল 18। এরকমভাবে সংখ্যা খোঁজ করাকে লিনিয়ার সার্চ বলা হয়।

যখন আমরা জানি যে, 67 এর ইন্ডেক্স হল 18, আমরা বুঝি যে এটি একটি মৌলিক সংখ্যা। এছাড়াও আমরা বুঝতে পারি যে, অ্যারেতে 67 এর আগে আরও 18 টি উপাদান রয়েছে, অর্থাৎ 67 এর আগে 18 টি ছোট মৌলিক সংখ্যা রয়েছে।

তুমি কি দেখেছ এতে কতগুলো ধাপ রয়েছে? বাইনারি সার্চ এটির থেকে আরও ভালো হবে। কারণ primes এর অ্যারেতে 25 টি সংখ্যা রয়েছে, এটির 0 থেকে 24 পর্যন্ত অ্যারের ইন্ডেক্স রয়েছে। আগের সুডোকোড ব্যবহার করে, আমরা min = 0 এবং max = 24 লেখি। বাইনারি সার্চের প্রথম অনুমান হবে 12 ইন্ডেক্সে (যা হল (0 + 24) / 2)। primes[12] কি 67 এর সমান? না, primes[12] সমান হল 41।

12 এর ইন্ডেক্স কি বড় না ছোট? অ্যারের মান বৃদ্ধি পায় এবং 41 < 67। সুতরাং, 67 মানটি 12 ইন্ডেক্সের ডানদিকে থাকা উচিত। অন্য কথায়, যে ইন্ডেক্স আমরা খুঁজছি সেটি 12 থেকে বৃহত্তর হওয়া উচিত। আমরা min এর মান 12 + 1 অথবা 13 করি এবং max এর 24 রাখি।

পরের ইন্ডেক্সটি কি হবে? 13 এবং 24 এর গড় হল 18.5, যাকে রাউন্ড করলে 18 হয়, অ্যারের ইন্ডেক্স অবশ্যই পূর্ণসংখ্যা হবে। আমরা জানি, primes[18] এর মান হল 67।

বাইনারি সার্চ অ্যালগোরিদম এখানে থেমে যায়, কারণ এটি উত্তর খুঁজে পেয়েছে। লিনিয়ার সার্চের 19 টি অনুমানের পরিবর্তে শুধুমাত্র দুইটি অনুমানের দরকার হয়েছে। নিজে প্রতিটি ধাপ দেখে তুমি আরও ভালোভাবে বুঝতে পার:

আমরা একটি উদাহরণ করে বাংলায় বাইনারি সার্চের অ্যালগোরিদম বর্ণনা করলাম। এটি একটি উপায়, কিন্তু মানুষের ভাষায় বর্ণনামূলক বিষয়গুলো ক্ষেত্র বিশেষে আলাদা হতে পারে। এটি বড় কিংবা ছোট হতে পারে, কিন্তু সবচেয়ে গুরুত্বপূর্ণ বিষয় হল এটি সবসময় নির্দিষ্ট নয়। আমরা তোমাকে যে কোন প্রোগ্রামিং ভাষা যেমন জাভাস্ক্রিপ্ট বা পাইথনে বাইনারি সার্চ দেখাতে পারতাম, কিন্তু প্রোগ্রামে অনেক ধরনের বিষয় থাকে - প্রোগ্রামিং ভাষার নিয়ম অনুযায়ী অর্থাৎ প্রোগ্রামকে উপাত্ত, ব্যবহারকারী অথবা সিস্টেমের ত্রুটি সামলাতে হয় - এবং এই সকল বিষয় শিখতে গিয়ে অ্যালগোরিদম শেখা কঠিন হয়ে পড়ে। এজন্য আমরা সুডোকোডে অ্যালগোরিদম বর্ণনা করি, যা বাংলা ও প্রোগ্রামিং ভাষার সংমিশ্রণে লেখা হয়।

একটি অ্যারেতে বাইনারি সার্চের মাধ্যমে খুঁজে দেখার জন্য পরিবর্তিত সুডোকোডটি এখানে দেওয়া হল। ইনপুট হিসেবে আমরা এখানে অ্যারে ব্যবহার করছি, যেটা হল array; array এর ভেতর n সংখ্যক উপাদান রয়েছে এবং target হল যে সংখ্যাটি সন্ধান করা হচ্ছে। এখানে আউটপুট হবে array এর ভেতর যেই ইনডেক্সে targetপাওয়া যাবে সেটি:

এই টিউটোরিয়ালে পরিস্থিতি সাপেক্ষে আমরা বাংলা, সুডোকোড এবং জাভাস্ক্রিপ্ট ব্যবহার করবো। প্রোগ্রামার হিসেবে, তোমাকে সুডোকোড বুঝে এটি যে কোন পছন্দনীয় ভাষায় লেখতে হবে - তাই যদিও আমরা এখানে জাভাস্ক্রিপ্ট ব্যবহার করছি, তুমি এই সুডোকোড অন্য ভাষাতেও রূপান্তর করতে পার।

আমরা সুডোকোডকে কীভাবে জাভাস্ক্রিপ্টে লেখবো? আমাদের একটি ফাংশন তৈরি করা উচিত, কারণ আমরা এমন কোড লেখছি যা ইনপুট নিয়ে আউটপুট রিটার্ন করে এবং আমরা চাই যেন উক্ত কোড বিভিন্ন ইনপুটের জন্য ব্যবহার করা যায়। ফাংশনের প্যারামিটার হবে—ধরি, binarySearch— এটি অ্যারে এবং লক্ষ্য (target) মান হবে এবং ফাংশন খুঁজে পাওয়া লক্ষ্য মানের ইন্ডেক্সের অবস্থানের মান রিটার্ন করবে।

এখন ফাংশনের বডি ও প্রয়োগ নিয়ে ভাবা যাক। ধাপ6, ধাপ 2 এ ফেরত যেতে বলে। এটিকে লুপের মত মনে হয়। এটির কি for লুপ নাকি while লুপ হওয়া উচিত? তুমি for লুপ চাইলে ব্যবহার করতে পার, কিন্তু এটি বাইনারি সার্চের খোঁজার প্রক্রিয়ার জন্য কিছুটা জটিল হয়। এটি ক্রমান্বয়ে লুপ চালানোর ক্ষেত্রে ভালো কাজ করে। কিন্তু এই ক্ষেত্রে আমরা কখনও ইন্ডেক্স 12 এবং তারপর 18, এভাবে হিসাব করতে পারি। এজন্য while লুপ উত্তম নির্বাচক।

সুডোকোডে আরেকটি গুরুত্বপূর্ণ ধাপ নেই যা অনুমানের খেলার জন্য দরকার হয়নি কিন্তু এটি বাইনারি সার্চের জন্য প্রয়োজনীয়। অ্যারেতে তোমার খোঁজ করা সংখ্যা খুঁজে না পেলে কি হবে? দেখা যাক এই ক্ষেত্রে binarySearch ফাংশনের কোন ইন্ডেক্স রিটার্ন করা উচিত। এটি এমন একটি সংখ্যা হতে হবে যা অ্যারেতে বৈধ ইন্ডেক্স নয়। আমরা -1 ব্যবহার করবো, যেন এটি অ্যারের কোন বৈধ ইন্ডেক্স না হয়। (আসলে যে কোন ঋণাত্মক সংখ্যাই কাজ করবে।)

অনুমান করা বাকি না থাকলে target সংখ্যাটি অ্যারেতে নেই। আমাদের উদাহরণে, ধরি আমরা target সংখ্যা হিসেবে 10 কে primes অ্যারেতে খুঁজছি। এটি থাকলে, 10 সংখ্যাটি 7 এবং 11 এর মধ্যে থাকত, যাদের ইন্ডেক্স হল 3 এবং 4। তুমি যদি min ও max এর ইন্ডেক্সের মান binarySearch ফাংশন চলাকালীন সময়ে খোঁজ কর, তাহলে তুমি দেখবে এমন এক সময় আসবে যখন min সমান 3 এবং max সমান 4\ হয়। তারপর অনুমান ইন্ডেক্স 3 (যেহেতু (3 + 4) / 2 সমান 3.5 এবং আমরা রাউন্ড করি) এবং primes[3] 10 থেকে ছোট, যাতে min এর মান 4\ হয়। উভয় min ও max 4 হলে, অনুমানকৃত ইন্ডেক্স হয় 4 এবং primes[4] এর মান 10\ থেকে বড়। এখন max এর মান 3\ হয়ে যায়। তাহলে min সমান 4 এবং max সমান 3 হলে এর অর্থ কি? এর অর্থ হল সম্ভাব্য অনুমানের সংখ্যা কমপক্ষে 4 অথবা 3\ হয়। এমন কোন সংখ্যা নেই! এই মুহূর্তে, আমরা বলতে পারি যে target সংখ্যাটি হল, 10, এটি primes অ্যারেতে নেই এবং binarySearch ফাংশন -1 রিটার্ন করে। সাধারণত, একবার max যদি min থেকে ছোট হয়, আমরা বুঝতে পারি যে, target সংখ্যাটি বিন্যস্ত অ্যারেতে নেই। এইখানে বাইনারি সার্চের এমন একটি সুডোকোড দেওয়া হল যা target সংখ্যা না থাকলেও কাজ করে:

এখন আমরা সুডোকোড সম্পর্কে জেনেছি, তোমার এবার নিজের চেষ্টায় বাইনারি সার্চ তৈরি করার পালা। সুডোকোড পুনরায় দেখা যাবে - আসলে, এটি দেখা ভালো, কারণ এটিকে দেখলেই তুমি বুঝে সঠিকভাবে কোড লেখতে পারবে।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।