Introduction

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

এই অ্যালগরিদম সম্পর্কে জানার জন্য আমরা একটা প্রব্লেম নিয়ে কাজ করবো। প্রব্লেমটি হলো - আমাদের কাছে একটা লিস্ট আছে কিছু এলিমেন্টের, সেটা হলো a1, a2, a3, ..., an। এখান থেকে আমাদেরকে বের করতে হবে x উপাদানটি আছে কিনা। যদি থেকে থাকে তাহলে কত নাম্বার পজিশনে সেটি আছে। যদি না থাকে তাহলে রেজাল্ট হবে ০।

Types of searching algorithms

প্রধানত দুই ধরণের সার্চিং অ্যালগরিদম আছে। যথাঃ

• Linear search or Sequential search
• Binary search

Linear Search or Sequential Search

এই অ্যালগরিদমের শুরুতে আমরা কম্পেয়ার করবো x এবং a1 এর মধ্যে। যদি x = a1 হয় তাহলে x এর পজিশন হবে ১ নম্বরে। যদি x != a1 হয়, তাহলে আমরা x এবং a2 এর মধ্যে কম্পেয়ার করবো। যদি x = a2 হয়, তাহলে x এর পজিশন হবে ২ নম্বরে। আর যদি সমান না হয়, তাহলে x এবং a3 এর মধ্যে কম্পারিজনে যাবো। এভাবে চলতে থাকবে যতক্ষণ পর্যন্ত x ম্যাচ না হয়। যে পজিশনে ম্যাচ হবে আমাদের সমস্যার সমাধান সেটা। আর যদি লিস্টে পাওয়া না যায় তাহলে উত্তর হবে ০। আমরা এই অ্যালগরিদমের সুডোকোড লিখার চেষ্টা করি এখন।

procedure linear search(x: integer, a1 , a2 , ... , an : distinct integers)
i := 1
while (i ≤ n and x ≠ ai )
    i := i + 1
if i ≤ n then location := i
else location := 0
return location{location is the subscript of the term that equals x, or is 0 if x is not found}

তাহলে আপনারা এই অ্যালগরিদমের নাম কেন লিনিয়ার সার্চ সেটা আশা করি বুঝতে পেরেছেন। এটা শুরু থেকে প্রতিটা এলিমেন্ট ধরে ধরে কম্পেয়ার করবে যতক্ষণ পর্যন্ত কাঙ্ক্ষিত সমাধান পাওয়া না যায়। তাই এর নাম লিনিয়ার বা সিকোয়েন্সিয়াল সার্চ।

Binary Search

এবার আমরা বাইনারি সার্চ অ্যালগরিদম সম্পর্কে জানবো। এটা কথা দিয়ে বুঝানো একটু কঠিন। একটা উদাহরণ দিয়ে বুঝাই। খুব সংক্ষেপে আগে কনসেপ্টটা বলে নিই। ধরেন আপনার কাছে ১০০টা নাম্বারের একটা ছোট থেকে বড় সর্টেড লিস্ট আছে। আপনাকে যেকোনো একটা নাম্বার খুঁজতে দেয়া হলো। আপনি সব নাম্বারকে অর্ধেক ভাগে ভাগ করে নিবেন। ১ম ৫০টা নাম্বার একদিকে, ২য় ৫০টা নাম্বার অন্যদিকে। এবার আপনি ১ম সাবলিস্টের সর্বোচ্চ নাম্বার অর্থাৎ লিস্টের মিডল নাম্বারের সাথে আপনার কাঙ্ক্ষিত নাম্বার কম্পেয়ার করবেন। যদি সেই মিডল নাম্বার আপনার কাঙ্ক্ষিত নাম্বার থেকে ছোট হয়, তাহলে ১ম অর্ধেক নাম্বারের লিস্ট বাদ। আমরা ২য় অর্ধ লিস্টে যাবো। সেটাকে আবার দুই ভাগ করবো। এভাবে করে দেখতে থাকবো ততক্ষণ যতক্ষণ পর্যন্ত কোনো সাবলিস্টে আমরা নাম্বারটি পাবো না। চলুন একটা উদাহরণ দেখি। তাহলে আপনাদের ক্লিয়ার হবে ব্যাপারটা।

ধরেন আমাদের কাছে একটা লিস্ট আছে। ১, ২, ৩, ৫, ৬, ৭, ৮, ১০, ১২, ১৩, ১৫, ১৬, ১৮, ১৯, ২০, ২২। মোটা ১৬টি নাম্বার আছে। আমাদের সার্চ করতে হবে ১৯ সংখ্যাটি। এবার আমরা ২ ভাগে ভাগ করবো এগুলোকে। একটা ভাগে থাকবে ১, ২, ৩, ৫, ৬, ৭, ৮, ১০ এবং অন্য ভাগে থাকবে ১২, ১৩, ১৫, ১৬, ১৮, ১৯, ২০, ২২। এবার আমরা ১ম লিস্টের সর্বোচ্চ সংখ্যার সাথে ১৯ কে কম্পেয়ার করবো। ১ম লিস্টের সর্বোচ্চ সংখ্যা হলো ১০, যেখানে ১০ < ১৯। সুতরাং ১৯ সংখ্যা ১ম লিস্টে থাকা সম্ভব নয়। অর্থাৎ অরিজিনাল লিস্টের ১ থেকে ৮ নাম্বার পজিশনে ১৯ সংখ্যাটি নেই। তাহলে ৯ থেকে ১৬ নম্বর পজিশনের মধ্যে ১৯ সংখ্যাটি আছে।

এবার আমরা ২য় সাবলিস্টে যাবো। গিয়ে ঐ সাবলিস্টকে আবার অর্ধেক ভাগে ভাগ করবো যার এক ভাগে থাকবে ১২, ১৩, ১৫, ১৬ এবং অন্য ভাগে থাকবে ১৮, ১৯, ২০, ২২। এবার ১ম সাবলিস্টের সর্বোচ্চ নাম্বার হলো ১৬, যেখানে ১৬ < ১৯। সুতরাং অরিজিনাল লিস্টের ৯ থেকে ১২ নাম্বার পজিশনের মধ্যেও ১৯ নেই। সুতরাং ১৩ থেকে ১৬ এর মধ্যে ১৯ আছে।

এবার ১৩ থেকে ১৬ পজিশনের নাম্বারগুলোকে দুই ভাগে ভাগ করবো যার এক ভাগে থাকবে ১৮, ১৯ এবং অন্যভাগে থাকবে ২০, ২২। আমরা ১ম সাবলিস্টে দেখছি সর্বোচ্চ নাম্বার ১৯ যা আমাদের কাঙ্ক্ষিত নাম্বার। তাহলে আমরা অরিজিনাল লিস্টের ১৩ এবং ১৪ নাম্বার পজিশনের সাবলিস্টে আমাদের নাম্বারটি পাচ্ছি। এই সাবলিস্টে আছে ১৮, ১৯ যাকে দুই ভাগ করলে এক ভাগে পাবো ১৮, যা অরিজিনাল লিস্টের ১৩তম নাম্বার এবং অন্যভাগে পাবো ১৯ যা আমাদের কাঙ্ক্ষিত নাম্বার এবং যার পজিশন অরিজিনাল লিস্টের ১৪তম। সুতরাং আমাদের কাঙ্ক্ষিত নাম্বার ১৯ আমাদেরকে প্রদত্ত লিস্টের ১৪ নাম্বার পজিশনে আছে।

এবার আমরা আমাদের প্রথমে দেয়া প্রব্লেমটা সলভ করি বাইনারি সার্চের মাধ্যমে। আমরা x কে কম্পেয়ার করবো লিস্টের মিডল টার্ম am এর সাথে কম্পেয়ার করবো, যেখানে m = [(n + 1) / 2]। যদি x > am হয় তাহলে আমরা আমাদের সেকেন্ড লিস্টে যাবো যেটা am+1, am+2, ..., an. আর যদি am > x হয় তবে আমরা প্রথম লিস্টেই স্ট্রিক্ট থাকবো যেটা হলো a1, a1, a3, ..., am। এভাবে করে চলতে থাকবে যতক্ষণ পর্যন্ত আমরা আমাদের সার্চিং আইটেম খুঁজে না পাচ্ছি। এই অ্যালগরিদমের সুডোকোড নিচে দেয়া হলো।

procedure binary search (x: integer, a1 , a2 , ... , an : increasing integers)
i := 1{i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while i < j
    m := ⌊(i + j) ∕ 2⌋
    if x > am then i := m + 1
    else j := m
if x = ai then location := i
else location := 0
return location{location is the subscript i of the term ai equal to x, or 0 if x is not found}

এই অ্যালগরিদমে আমাদের প্রতিটা আইটেম ধরে ধরে কম্পেয়ার করতে হচ্ছে না। আমরা আমাদের লিস্টকে দুই ভাগে ভাগ করে শুধু সর্বোচ্চ নাম্বার কম্পেয়ার করবো। যে ভাগের সর্বোচ্চ নাম্বার আমাদের কাঙ্ক্ষিত নাম্বারের চেয়ে বড় বা এর সমান হবে আমরা শুধু সেই ভাগ নিয়েই কাজ করবো। অন্য ভাগ নিয়ে আমাদের চিন্তা করারই কোনো প্রয়োজন নেই।

আশা করি আমরা সার্চিং অ্যালগরিদম নিয়ে মোটামুটি একটা ধারণা পেয়েছেন। এই অ্যালগরিদম আমাদের কম্পিউটার প্রোগ্রামিং এর ক্ষেত্রে প্রায়ঃশই ব্যবহৃত হয়।