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

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. We used binary search in the guessing game in the introductory tutorial.

One of the most common ways to use binary search is to find an item in an array. For example, the Tycho-2 star catalog contains information about the brightest 2,539,913 stars in our galaxy. Suppose that you want to search the catalog for a particular star, based on the star's name. If the program examined every star in the star catalog in order starting with the first, an algorithm called linear search, the computer might have to examine all 2,539,913 stars to find the star you were looking for, in the worst case. If the catalog were sorted alphabetically by star names, binary search would not have to examine more than 22 stars, even in the worst case.

পরবর্তী কয়েকটি অনুচ্ছেদে আলোচনা করা হবে কীভাবে যত্নসহকারে অ্যালগোরিদম বর্ণনা করা হয়, কীভাবে অ্যালগোরিদম জাভাস্ক্রিপ্টে বাস্তবায়ন করা যায় এবং কীভাবে কর্মদক্ষতা বিশ্লেষণ করা যায়।

একটি অ্যালগোরিদম একজনকে বোঝানোর সময়, একটি অসম্পূর্ণ বর্ণনা মাঝে মাঝে যথেষ্ট হয়ে যায়। কেক বানানোর রেসিপি থেকে কিছু বিস্তারিত বর্ণনা হয়তো বাদ পড়তে পারে; রেসিপি ধরে নেয় যে তুমি রেফ্রিজারেটর হতে ডিম বের করা এবং ডিম ভাঙার উপায়টি জানো। মানুষ স্বজ্ঞাতভাবে জানে কি করে না বলা বর্ণনাগুলো পূরণ করতে হয়, কিন্তু কম্পিউটার প্রোগ্রাম সেটা জানেনা এবং এ কারণে কম্পিউটারকে পুরো অ্যালগোরিদম বর্ণনা করতে হয়।

একটি অ্যালগোরিদমকে প্রোগ্রামিং ভাষায় বাস্তবায়নের জন্য অ্যালগোরিদমটিকে বিস্তারিতভাবে বোঝা আবশ্যক। সমস্যার ইনপুটগুলো কি? আউটপুটগুলো কি? কোন চলকটি তৈরি করা উচিত এবং তাদের প্রাথমিক কোন মান থাকা উচিত? কোন ধাপগুলো অন্য মান এবং সর্বশেষ ফলাফল হিসাব করার জন্য অনুসরণ করতে হবে? এই ধাপগুলো কি এমন কোন নির্দেশনার পুনরাবৃত্তি করছে যা কোন লুপ ব্যবহার করে সহজে লেখা যেত?

চল দেখা যাক কীভাবে যত্ন সহকারে বাইনারি সার্চ বর্ণনা করা যায়। বাইনারি সার্চের আসল ধারনাটি হল বর্তমান রেঞ্জে যৌক্তিক অনুমানের গতিবিধি অনুসরণ করা। ধরি, 1 থেকে 100 পর্যন্ত একটি সংখ্যার কথা চিন্তা করা হচ্ছে, সম্পূর্ণ অনুমানের খেলার মত। যদি তুমি ইতোমধ্যে 25 অনুমান কর এবং আমি বলি যে, আমার সংখ্যাটি এর থেকে বড় ছিল, তারপর তুমি অনুমান করলে 81 এবং আমি তোমাকে বললাম আমার সংখ্যাটি এর থেকে ছোট, তাহলে 26 হতে 80 এর রেঞ্জের সংখ্যাগুলো হবে যৌক্তিক অনুমান। এখানে, এই সংখ্যা রেখার লাল অংশটি যৌক্তিক অনুমান ধারণ করছে এবং কালো অংশটি বাতিল অনুমানগুলো দেখায়:

প্রত্যেকবারে, তুমি একটি অনুমান করেছ যা যৌক্তিক অনুমানগুলোকে মোটামুটি সমান আকারে দুইটি রেঞ্জে বিভক্ত করেছে। যদি তোমার অনুমান সঠিক না হয়, তাহলে আমি তোমাকে বলবো এটি খুব বেশি কিংবা খুব কম কিনা। তাহলে তুমি যৌক্তিক অনুমানের প্রায় অর্ধেক বাদ দিয়ে দিতে পারবে। উদাহরণস্বরূপ, যদি যৌক্তিক অনুমানের রেঞ্জ 26 থেকে 80 হয়, তাহলে তুমি অনুমান করবে যে এর মধ্যবিন্দু, $(26+80)/2$‍ অথবা 53। যদি আমি বলি 53 অনেক বেশি, তাহলে তুমি রেঞ্জটিকে অর্ধেক করে 26 হতে 52 সংখ্যাটিকে যৌক্তিক অনুমানের নতুন রেঞ্জ হিসেবে ধরে নিয়ে 53 থেকে 80 পর্যন্ত সকল সংখ্যা বাদ দিতে পারবে।

অনুমানের খেলার ক্ষেত্রে, আমরা কিছু চলক ব্যবহারের মাধ্যমে যৌক্তিক অনুমানের সেটকে অনুসরণ করতে পারি। ধরা যাক, এই ধাপের জন্য চলক $min$‍ হল বর্তমান সর্বনিম্ন যৌক্তিক অনুমান এবং $max$‍ হল সর্বোচ্চ যৌক্তিক অনুমান। এই সমস্যার input হল $n$‍ সংখ্যা, সর্বোচ্চ সম্ভাব্য সংখ্যা যেটা তোমার প্রতিপক্ষ চিন্তা করছে। আমরা ধারণা করছি যে, সর্বনিম্ন সম্ভাব্য সংখ্যা হল 1, কিন্তু এটা খুবই সহজ হত যদি সর্বনিম্ন সম্ভাব্য সংখ্যাটিকে দ্বিতীয় ইনপুট হিসেবে নেওয়ার জন্য অ্যালগোরিদমটিকে বদলানো যেত।

Here's a step-by-step description of using binary search to play the guessing game:

We could make that description even more precise by clearly describing the inputs and the outputs for the algorithm and by clarifying what we mean by instructions like "guess a number" and "stop." But this is enough detail for now.

Next up, we'll see how we can use binary search on an array, and discuss how to turn descriptions of algorithms into actual working code.

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