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

আচ্ছা আমরা কোন কিছু কিভাবে খুঁজি?আপনাকে বলা হলো ২্‌,৫,৩,৪,৮ সংখ্যাগুলোর মধ্যে ৮ এর অবস্থান কোথায়।বা ৮ কে খুঁজে বের কর।চট করে দেখে বলা যায় যে ৮ সংখ্যাগুলোর মধ্যে শেষে কিংবা ৫ নম্বর(index) এ অবস্থিত।অনুরূপ ভাবে ৫, ইনডেক্স ২ এ অবস্থিত।

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

লিনিয়ার সার্চ  করতে পারেন, যদি না আপনার কাছে অনেক সময় থাকে।কল্পনা করুন আপনার লিস্ট এ ৫০০+ সংখ্যা আছে।আর আপনি যদি এভাবে খোঁজ চালাচ্ছেন।একটু চিন্তা করলেই বোঝা যায় এইভাবে খোঁজা কতটা সময়-সাপেক্ষ এবং ঝামেলার।যদি এই সমস্যার সমাধান চান তাহলে আপনার জন্য এই হ য ব র ল লেখাটা।

আমরা সবাই ডিকশনারিতে শব্দ খুঁজেছি।ডিকশনারিতে চট করে শব্দ খুঁজে বের করা যায়।খুব বেশি সময় লাগেনা। কেন? ডিকশনারিতে কেন কম সময়ে হাজার হাজার শব্দের  মধ্যে আমরা আমাদের নিদিষ্ট শব্দ খুঁজে পাই।এর পিছনে কারন হলো ডিকশনারিতে একটা বিশেষ উপায়ে শব্দগুলো সাজানো  থাকে।শব্দ গুলা অক্ষর অনুযায়ী সাজানো। এজন্য আমরা আমাদের নিদিষ্ট শব্দের  একটা অবস্থান সম্পর্কে ধারনা পাই।ফলে সহজে আমরা ওই শব্দ টার অবস্থান জানতে পারি।

যদি আপনি ডিকশনারিতে Love শব্দটা খুঁজতে চান।এবং আপনি আন্দাজে Hate শব্দটা খুঁজে পেয়েছেন।এখান থেকে সহজে অনুমান করা যায় যে Love শব্দ টার অবস্তান Hate এর পরে।কারণ ইংরেজি শব্দে L এর আগে H। এমন করে আমরা ডিকশনারিতে যেকোন শব্দ কম সময়ে খুঁজে পাই। তাহলে দেখা যাচ্ছে যে শব্দ গুলো বিশেষ উপায়ে সাজানোর ফলে খুঁজতে সুবিধা।

এখন আমরা সেই সংখ্যার তালিকাতে ফিরে যাই। ডিকশনারিতে যেমন বিশেষ উপায়ে সাজিয়ে সহজে শব্দের অবস্থান পাওয়া যাচ্ছে,তেমন কোন ভাবে আমাদের সংখ্যার তালিকা কে সাজিয়ে সহজে খোঁজ করা যাবে? হ্যাঁ যাবে। ধরুন আমাদের তালিকাটা এমন **[২,১,৫্‌,৩,৬,৮,৯,৩৪,৬৩,১০০,৫০০.........]**(অনেক বড় তালিকা)।এটাকে যদি ছোট থেকে বড়তে সাজানো হলো(**[১,২,৩,৫,৬,৮,৯,৩৪,৬৩,১০০,৫০০]**)।ফলে আমরা চট করে যেকোন সংখ্যার অবস্থান সম্পর্কে ধারনা পাবো।যদি ৫০০ কে খুঁজতে বলা হয় এবং প্রথমে ৩৪ খুঁজে পাই তাহলে আমরা বুঝতে পারবো ৫০০ এর অবস্থান ৩৪ এর ডানে বা পরে।এভাবে ডিকশনারির মতো করে খুঁজতে পারবো।কিন্তু তালিকা আরও বড় হলে কি হবে? কি করে আর দ্রুত খুঁজে পাওয়া যাবে?

দেখুন আগে আমরা **৩৪** এর অবস্থান দেখে **৫০০** এর অবস্থান সম্পর্কে ধারনা পেয়েছি।এখন আমরা তালিকার মাঝের সংখ্যাটা দেখা যাক।মাঝের সংখ্যাটি হলো **৮**(যেহেতু আমাদের লিস্ট এর সাইজ **১১** সুতরাং মাঝের ইনডেক্স হলো ৬)।এখন দেখি ৮ থেকে ৫০০ বড় না ছোট।যদি বড় হয় তাহলে অবশ্যই ৫০০ এর অবস্থান ৮ এর পরে(যেহেতু ছোট থেকে বড় সাজানো)।এখন আমরা তালিকাকে ২ ভাগে ভাগ করি ৮ কে কেন্দ্র করে।

ভাগ করার পর তালিকা-

**   [ ১,২,৩,৫,৬] ,৮, [৯,৩৪,৬৩,১০০,৫০০]**

এখন আমাদের ৫০০ কে ৮ এর ডানের তালিকায় অবস্থান করা উচিত।এখন আমরা ৮ সহ বামের(৮ এর বামের) তালিকাটা বাদ দেই।

**  [৯,৩৪,৬৩,১০০,৫০০]**

আবার এই তালিকার মাঝের সংখ্যা ৬৩ সুতরাং ৫০০ এর অবস্থান ৬৩ এর পরে।আবার তালিকাকে ২ ভাগে ভাগ করি।

**  [৯,৩৪],৬৩,[১০০,৫০০]**

অনুরূপ ভাবে ৫০০ ডানের তালিকায় অবস্থান করবে।এবারো ৬৩ সহ ডানের তালিকাকে দুর করি ।[১০০,৫০০]।এই তালিকা থেকে ৫০০ খুঁজে বের করা খুব সহজ (আবার দুভাগে ভাগ করে)। এখন দেখা যাচ্ছে তালিকা বারবার ২ ভাগে ভাগ করে কম সময়ে আমরা খুঁজে পাচ্ছি। এভাবে খোঁজার পদ্ধতি কে আমরা বলি "বাইনারি সার্চ"।বাইনারি সার্চ করে করে আমরা n সাইজ এর তালিকা থেকে O(log2n) বারে আমরা আমাদের নিদিষ্ট সংখ্যার অবস্থান এর খোঁজ পাবো।যেমন এখানে ১১ সাইজ এর তালিকা থেকে আমরা ৩ বারে(৩ বার তালিকা কে ২ ভাগে ভাগ করেছি) ৫০০ খুঁজে পেয়েছি।lO(log2n) = 3.4।সুতরাং বলা যায় বাইনারি সার্চ অ্যালগরিদম এর কমপ্লেক্সিটি O(log2n)।( সর্টিং এর কমপ্লেক্সিটি বাদে)। লিনিয়ার সার্চ এ কমপ্লেক্সিটি হলো O(n)।এখন যেহেতু সর্ট ছাড়া বাইনারি সার্চ করা সম্ভব না। আবার একটা অ্যারে কে O(n * log2 (n)) কম কমপ্লেক্সিটিতে সর্ট করা যাবে না।তাহলে বাইনারি সার্চ কেন করবো।লিনিয়ার সার্চ করলেই তো হয়।যদি একবার সার্চ করতে হয় তাহলে লিনিয়ার সার্চ করাই ভালো।কিন্তু যদি বারবার সার্চ করার প্রয়োজন তাহলে বাইনারি সার্চ করাই উচিত।আর তালিকা কে সবসময় সর্ট করে রাখাই বুদ্ধিমানের কাজ।এখানে O(log2n) হবার কারণ হলো কোন সংখ্যা কে আমরা ২ দিয়ে ভাগ করছি যতক্ষণ না ১ হচ্ছে।

পাইথন কোডে বাইনারি সার্চ এর ইমপ্লেমেন্টেশন-

def binary_search(array, key):

    Start = 0

     End = len(array)-1

     Index = None

     while begin<=end:

           mid=(begin+end)/2

           if key == array[mid]:

           index=mid #The value is found, save the index.

           break

           elif key > array[mid]: begin=mid+1 #Search the right portion

           elif key < array[mid]: end=mid-1 #Search the left portion

 return index #If the number is not found, index will contain None.

info=[100,2,10,50,20,500,100,150,200,1000,100]

info=sorted(info)#ছোট থেকে বড়তে সাজানো হয়েছে

while True:

   key = int(raw_input())

   print search(info,key)

এই পর্যন্ত যদি পড়ে থাকেন তাহলে ধন্যবাদ।ভুলত্রুটি হলে ক্ষমা চাচ্ছি।

Writer: Fahim Ihtesham Sohan