আমরা জানি, n উপাদান বিশিষ্ট কোন অ্যারেতে লিনিয়ার সার্চ প্রয়োগ করলে এটির অনুমান সংখ্যাও হয় n। এতক্ষণে হয়তো তুমি জানো যে, লিনিয়ার সার্চ এর চেয়ে বাইনারি সার্চের কম সংখ্যক অনুমান দরকার হয়। বড় অ্যারের ক্ষেত্রে লিনিয়ার সার্চ ও বাইনারি সার্চের পার্থক্য আরও স্পষ্ট হয়। দেখা যাক, কিভাবে বাইনারে সার্চের সর্বোচ্চ অনুমান সংখ্যা নির্ণয় করা যায়।
বাইনারে সার্চের মূল বিষয় হল, কোন ভুল অনুমান করা হলে অ্যারের সঠিক অনুমান করা অংশটুকু বিভক্ত করে অর্ধেকে পরিণত করা হয়। যদি সঠিক অনুমানের অংশে ৩২ টি উপাদান থাকে, তাহলে ভুল অনুমান এটিকে বিভক্ত করে ১৬ টি উপাদানে পরিণত করে। প্রতিটি ভুল অনুমানের জন্য বাইনারি সার্চ অ্যারেকে বিভক্ত করে অর্ধেকে পরিণত করে।
৮ দৈর্ঘ্যের অ্যারে নেওয়া হলে, ভুল অনুমান এটিকে ৪, পরে ২ এবং তারপর ১ টি আনুমানিক অংশে বিভক্ত করে যার মধ্যে সঠিক উপাদানটি অবস্থান করে। অনুমান করা অংশে যখন মাত্র একটি উপাদান থাকে, আর কোন অনুমান ঘটে না; অনুমান করা একটি উপাদান হয় সঠিক অথবা ভুল এবং এখানেই শেষ। সুতরাং, ৮ দৈর্ঘ্যের অ্যারেতে, সর্বোচ্চ চারটি অনুমান দরকার হয়।
১৬ টি উপাদানের অ্যারের কি হবে? প্রথম অনুমান ৮ টি উপাদানকে বাদ দেবে ধারণা করলে তুমি সঠিক চিন্তা করেছ। ১৬ টি উপাদানের অ্যারের জন্য সর্বোচ্চ পাঁচটি অনুমান দরকার।
এখন হয়তো তুমি একটি প্যাটার্ন দেখতে পাবে। প্রতিবার অ্যারের আকার দ্বিগুণ করলে, আমাদের সর্বোচ্চ আরও একটি অনুমানের প্রয়োজন হয়। ধরি, আমাদের n দৈর্ঘ্যের অ্যারের জন্য সর্বোচ্চ m সংখ্যক অনুমান দরকার। তাহলে, 2, n দৈর্ঘ্যের অ্যারেকে প্রথম অনুমান n দৈর্ঘ্যে পরিণত করে এবং সর্বোচ্চ m অনুমান দরকার হয়, যা মোট হল m, plus, 1 সংখ্যক অনুমান।
একটি সাধারণ n দৈর্ঘ্যের অ্যারে দেখা যাক। আমরা অনুমানের সংখ্যাকে, ওরস্ট কেসে, "n থেকে শুরু করে একদম 1 পাওয়া পর্যন্ত যে সংখ্যকবার পুনরায় অর্ধেক করতে পারি তার সাথে আরও ১ যোগ।" দ্বারা প্রকাশ করতে পারি। কিন্তু এটি লেখা জটিল। সৌভাগ্যক্রমে, পুনরায় অর্ধেক করার জন্য একটি গাণিতিক ফাংশন রয়েছে, যা n থেকে শুরু করে, মান 1 হওয়া পর্যন্ত কাজ করে: n এর ভিত্তি-২ এর লগারিদম। এটিকে লেখা হয়: lgn \lg n । (লগারিদমের সম্পর্কে আরও জানতে চাইলে এখানে ক্লিক কর।)
নিচের সারণিতে n এর বিভিন্ন মানের জন্য ভিত্তি-২ লগারিদমের মানগুলো দেওয়া হল:
nlgn \lg n
10
21
42
83
164
325
646
1287
2568
5129
102410
1,048,57620
2,097,15221
আমরা এই সারণিকে একটি লেখ হিসেবে বিবেচনা করে পাই:
n এর ছোট মানের দিকে লক্ষ্য করি:
লগারিদমের ফাংশন অনেক ধীরে বৃদ্ধি পায়। লগারিদম হল সূচকের বিপরীত, যা অনেক দ্রুত বৃদ্ধি পায়, যদি lgn=x \lg n = x হয়, তাহলে n, equals, 2, start superscript, x, end superscript হবে। উদাহরণস্বরূপ, lg128=7 \lg 128 = 7 হওয়ার কারণে, আমরা জানি, 2, start superscript, 7, end superscript, equals, 128
n যদি 2 এর ঘাত না হয়, আমরা 2 এর পরবর্তী বড় ঘাতে যেতে পারি। 1000 দৈর্ঘ্যের অ্যারের জন্য, 2 এর পরবর্তী বড় ঘাত হল 1024, যা সমান 2, start superscript, 10, end superscript। সুতরাং, 1000-উপাদান বিশিষ্ট অ্যারেতে, বাইনারি সার্চের মূলত 11 (10 + 1) টি অনুমান দরকার। টাইকো ২ (Tycho-2) তারার তালিকায় ছায়াপথের উজ্জ্বলতম 2,539,913 টি তারার ক্ষেত্রে, 2 এর পরবর্তী বড় ঘাত হল 2, start superscript, 22, end superscript (যা হল 4,194,304) এবং আমাদের সর্বোচ্চ 23 টি অনুমান দরকার। লিনিয়ার সার্চ থেকে বহুগুণে ভালো! নিচে তুলনা উল্লেখ করা হল:
পরবর্তী টিউটোরিয়ালে, আমরা দেখবো কিভাবে কম্পিউটার বিজ্ঞানীরা একটি চিহ্ন ব্যবহার বাইনারি সার্চ ও লিনিয়ার সার্চের চলার সময় বর্ণনা কর যা, অন্যান্য বিষয় থেকে চলার সময়কেই বেশি প্রাধান্য দেয়।

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