বাইনারি সার্চের রান করার সময়কাল

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

বাইনারে সার্চের মূল বিষয় হল, কোন ভুল অনুমান করা হলে অ্যারের সঠিক অনুমান করা অংশটুকু বিভক্ত করে অর্ধেকে পরিণত করা হয়। যদি সঠিক অনুমানের অংশে 32 টি উপাদান থাকে, তাহলে ভুল অনুমান এটিকে বিভক্ত করে 16 টি উপাদানে পরিণত করে। প্রতিটি ভুল অনুমানের জন্য বাইনারি সার্চ অ্যারেকে বিভক্ত করে অর্ধেকে পরিণত করে।

8 দৈর্ঘ্যের অ্যারে নেওয়া হলে, ভুল অনুমান এটিকে 4, পরে 2 এবং তারপর 1 টি আনুমানিক অংশে বিভক্ত করে যার মধ্যে সঠিক উপাদানটি অবস্থান করে। অনুমান করা অংশে যখন মাত্র একটি উপাদান থাকে, আর কোন অনুমান ঘটে না; অনুমান করা একটি উপাদান হয় সঠিক অথবা ভুল এবং এখানেই শেষ। সুতরাং, 8 দৈর্ঘ্যের অ্যারেতে, সর্বোচ্চ চারটি অনুমান দরকার হয়।

16 টি উপাদানের অ্যারের কি হবে? প্রথম অনুমান 8 টি উপাদানকে বাদ দেবে ধারণা করলে তুমি সঠিক চিন্তা করেছ। 16 টি উপাদানের অ্যারের জন্য সর্বোচ্চ পাঁচটি অনুমান দরকার।

এখন হয়তো তুমি একটি প্যাটার্ন দেখতে পাবে। প্রতিবার অ্যারের আকার দ্বিগুণ করলে, আমাদের সর্বোচ্চ আরও একটি অনুমানের প্রয়োজন হয়। ধরি, আমাদের $n$‍ দৈর্ঘ্যের অ্যারের জন্য সর্বোচ্চ $m$‍ সংখ্যক অনুমান দরকার। তাহলে, $2n$‍ দৈর্ঘ্যের অ্যারেকে প্রথম অনুমান $n$‍ দৈর্ঘ্যে পরিণত করে এবং সর্বোচ্চ $m$‍ অনুমান দরকার হয়, যা মোট হল $m+1$‍ সংখ্যক অনুমান।

Let's look at the general case of an array of length $n$‍. We can express the number of guesses, in the worst case, as "the number of times we can repeatedly halve, starting at $n$‍, until we get the value 1, plus one." But that's inconvenient to write out.

Fortunately, there's a mathematical function that means the same thing as the number of times we repeatedly halve, starting at $n$‍, until we get the value 1: the base-2 logarithm of $n$‍. That's most often written as ${\log }_{2}n$‍, but you may also see it written as $\lg n$‍ in computer science writings. (Want to review logarithms? Learn more here.)

নিচের সারণিতে $n$‍ এর বিভিন্ন মানের জন্য ভিত্তি-2 লগারিদমের মানগুলো দেওয়া হল:

We can view this same table as a graph:

n এর ছোট মানের দিকে লক্ষ্য করি:

The logarithm function grows very slowly. Logarithms are the inverse of exponentials, which grow very rapidly, so that if ${\log }_{2}n=x$‍, then $n=2^x$‍. For example, because ${\log }_{2}128=7$‍, we know that $2^7=128$‍.

That makes it easy to calculate the runtime of a binary search algorithm on an $n$‍ that's exactly a power of 2. If $n$‍ is 128, binary search will require at most 8 (${\log }_{2}128+1$‍) guesses.

What if $n$‍ isn't a power of 2? In that case, we can look at the closest lower power of 2. For an array whose length is 1000, the closest lower power of 2 is 512, which equals $2^9$‍. We can thus estimate that ${\log }_{2}1000$‍ is a number greater than 9 and less than 10, or use a calculator to see that its about 9.97. Adding one to that yields about 10.97. In the case of a decimal number, we round down to find the actual number of guesses. Therefore, for a 1000-element array, binary search would require at most 10 guesses.

For the Tycho-2 star catalog with 2,539,913 stars, the closest lower power of 2 is $2^{21}$‍ (which is 2,097,152), so we would need at most 22 guesses. Much better than linear search!

Compare $n$‍ vs ${\log }_{2}n$‍ below:

পরবর্তী টিউটোরিয়ালে, আমরা দেখবো কীভাবে কম্পিউটার বিজ্ঞানীরা একটি চিহ্ন ব্যবহার বাইনারি সার্চ ও লিনিয়ার সার্চের চলার সময় বর্ণনা কর যা, অন্যান্য বিষয় থেকে চলার সময়কেই বেশি প্রাধান্য দেয়।

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