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

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

মনে করেন আপনাকে একটি এরে দেওয়া হল যেখানে নিজের ভ্যালু গুলা আছে

এবং আপনাকে বলা হলো এই এরেতে ভ্যালু ৯আছে কিনা খুজে দেখতে বলা হয়েছে । এরেটি কে আমরা ছোট থেকে বড় আকারে সাজালে এখানে একটি সুন্দর টেকনিক সম্পর্কে আমরা জানতে পারবো , আসেন এরে টি কে সর্ট করে নেয়।

এখন আমরা একটা কাজ করতে পারি , আমাদের যেহেতু 7 আছে কিনা দেখতে বলা হয়েছে , আমরা এরে এর ঠিক মাঝখানের ভ্যালু টি নিয়ে চেক করে দেখবো এটি 7 কিনা। মাঝের ভ্যালুটি থাকবে = (0+6) /2 = 3 নাম্বার ইন্ডেক্সে।

এখানে মাঝখানের ভ্যালুটি হলো ৫ যা 7 এর সমান নয়।

এখন আসেন আমরা এরে থেকে কিছু প্রশ্ন করি

• প্রথম প্রশ্ন , আমরা যেহেতু মাঝখানে ভ্যালু ৫ পেয়েছি যা আমাদের কাঙ্খিত ভ্যালু ৭ এর থেকে কম। এখন কি মনে হয় মধ্যখানের বাম পাশে যে ভ্যালু গুলা আছে তার মধ্যে ৭ কে খুজে পাওয়ার কোনো সম্ভাবনা আছে কি ? -> যেহেতু আমরা যে ভ্যালু খুজছি ৭ তা ৫ থেকে বড় এবং ৫ এর বাম পাশে যে ভ্যালু গুলা আছে তা সব ৫ থেকেই ছোট তাই এরেটির ৫ এর বাম পাশের অংশটুকু তে কখনো ৭ ভ্যালুটি পাওয়া সম্ভব না।

• দ্বিতীয় প্রশ্ন , যদি আমরা এতটুকু নিশ্চিত থাকি যে , এরে এর মধ্যখানে ভ্যালু ৫ এর বাম পাশে সব ৫ হতে ছোট ভ্যালু এবং সেখানে ৭ ভ্যালুটি খুজে পাওয়া কখনো সম্ভব না, আমাদের ৯ ভ্যালুটি খোজার জন্য আবার এরে এর প্রথম থেকে পুরো ভ্যালুটি খুজতে হবে ? -> উত্তর হলো না, আমরা যেহেতু নিশ্চিত যে এরে এর মধ্যখানের ভ্যালুটি ৫ এবং এর বাম পাশে সব ৫ থেকে ছোট ভ্যালু তাই আমরা তার বাম পাশে আর ৭ খুজবো না। আমরা ৫ এর ডান পাশের অংশটি তে ৭ পাওয়া যায় কিনা খুজে দেখবো। অর্থাৎ আমরা আমাদের এরে এর searching space টি কে এখন অর্ধেক করে ফেললাম।

আমরা এখন এরেটির নিচের এই অংশের মধ্যে ভ্যালু ৭ খুজবো

এরপর আমরা আবার একই ভাবে মধ্যখানের ভ্যালুটি চেক করে দেখবো । মধ্য খানের ভ্যালু টি থাকবে (4+6) /2= 10/2 = 5 নাম্বার ইন্ডেক্সে। এখন চেক করে দেখবো এরেটির 5 নাম্বার ইনডেক্সে ভ্যালু ৭ আছে কিনা। এরেটির 5 নাম্বার ইনডেক্সে ৯ ভ্যালুটি আছে। আবার আগের মতো চিন্তা করে দেখি ,

• আমাদের এরেটি ছোট থেকে বড় আকারে সাজানো হয়েছে এবং আমরা আমাদের searching space এর মধ্য খানে পেয়েছি ৯ , অর্থাৎ ৯ এর বাম পাশের সব ভ্যালু হবে ৯ হতে ছোট এবং ডান পাশের সব ভ্যালু গুলা হবে ৯ এর থেকে বড়

• যেহেতু আমরা ভ্যালু ৭ কে খুজছি এবং ৭, ৯ হতে ছোট । সুতারাং এটি আমরা নিশ্চিত যে , ৯ এর ডান পাশে কখনো ভ্যালু ৭ পাওয়া সম্ভব না। আমরা ৯ এর বাম পাশে ভ্যালু ৭ খুজবো। অর্থাৎ আমরা আবারো আমাদের searching স্পেস কে অর্ধেক করে ফেললাম।

আমরা এখন এরেটির নিচের এই অংশের মধ্যে ভ্যালু ৭ খুজবো

এখন এরের এই অংশটুকুর মধ্য হচ্ছে (4+4)/2 = 8/2 = 4 নাম্বার ইন্ডেক্স। যা আমাদের কাঙ্খিত ভ্যালু 7 এর সমান।

টাইম কমপ্লেক্সিটি :

এখানে যেহেতু আমরা আমাদের প্রত্যেকটি স্টেপ পর পর এরে টির অর্ধেক অংশ কে বাদ দিয়ে দিচ্ছি এবং আমরা জানি যে , যদি এমন হয় প্রত্যেকটা স্টেপ পর পর যদি আমাদের কোন একটা ভ্যরিয়েবল এর মান অর্ধেক হারে কমতে থাকে তবে ঐ কোডের টাইম কমপ্লেক্সিটি হবে O(logn)। বাইনারি সার্চের ক্ষেত্রে আমাদের এরে এর যে অংশ টুকু তে মানটি খুজছি অর্থাৎ আমাদের searching space প্রতিটি স্টেপ এ অর্ধেক হয়ে যাচ্ছে। তাই

বাইনারি সার্চের টাইম কমপ্লেক্সিটি হলো O (logN )