ডাটা স্ট্রাকচার - Data structures

টারনারি সার্চ (Ternary search) অ্যালগরিদম

Ternary search Bangla tutorial / Ternary search algorithm / Search in a sorted array

টারনারি সার্চ (Ternary search) অ্যালগরিদম হলো এমন একটি সার্চ অ্যালগরিদম যেখানে আমরা আমাদের সার্চ রেঞ্জকে (যেই রেঞ্জে আমরা সার্চ করি তাই সার্চ রেঞ্জ) তিনভাগে ভাগ করে সার্চ করে। আমরা আগের লিখা, বাইনারি সার্চে দেখেছিলাম আমরা আমাদের রেঞ্জকে দুই ভাগে ভাগ করেছি। একটি ভাগ mid এর বামে, আরেকটি ডানে।

তবে টারনারি সার্চের ক্ষেত্রে আমরা আমাদের সার্চ রেঞ্জে (বা অ্যারের যেটুকুতে আমরা আছি) দুইটি পয়েন্ট নিবো। একটি mid_1 এবং আরেকটি mid_2 mid_1 এবং mid_2 দ্বারা আমাদের অ্যারে তিন ভাগে ভাগ হবে, প্রথম অংশ হবে সর্বনিম্ন রেঞ্জ বা l থেকে mid_1 পর্যন্ত। তারপর দ্বিতীয় অংশ mid_1 থেকে mid_2 এবং তৃতীয় অংশ হবে mid_2 থেকে সর্ব ডানের রেঞ্জ বা r

Ternary search Bangla Tutorial

টারনারি সার্চ একটি ভাগ কর শাসন করো বা Divide and conquer অ্যালগরিদম। বাইনারি সার্চের থেকে এর খুব বেশি একটা তফাত নেই। তাই এটা পড়ার আগে বাইনারি সার্চ নিয়ে জানা থাকলে সুবিধা পাবেন।

বাইনারি সার্চের মতো টারনারি সার্চ অ্যালগরিদমে কাজ করতে হলে আমাদের সর্টেড অ্যারে দরকার হয়। ধরা যাক আমাদের n সাইজের কোনও অ্যারে থেকে একটি সংখ্যা x কে খুঁজে বের করতে হবে। আমরা প্রতিবার নিচের মতো করে স্টেপ নিবো,

টারনারি সার্চ অ্যালগরিদম (Ternary search algorithm)

  1. অ্যারেটাকে সর্ট করে নিই।
  2. প্রথমে l=0 এবং r=n-1 [ শুন্য ভিত্তিক ইন্ডেক্সিং ]
  3. যতক্ষণ l\leq r হয় ততক্ষণ আমরা …
    1. mid_1 এবং mid_2 বের করি নিচের সূত্র মতো।
      mid_1 = l+ \lfloor \frac{ r-l }{3} \rfloor
      mid_2 = r – \lfloor \frac{ r-l }{3} \rfloor
    2. mid_1 এর সাথে আমরা x কে তুলনা করি। যদি Array[mid_1] আমাদের x এর সমান হয় তবে true রিটার্ন করি। নয়তো পরের ধাপে যাই।
    3. mid_2 এর সাথে আমরা x কে তুলনা করি। যদি Array[mid_2] আমাদের x এর সমান হয় তবে true রিটার্ন করি। না হলে পরের ধাপে যাই।
    4. যদি x এর মান Array[mid_1] এর থেকে ছোট হয় তাহলে আমরা বামে যাবো। ( r=mid_1 -1 সেট করতে হবে)
    5. অথবা যদি x এর মান Array[mid_2] এর থেকে বড় হয় তবে ডানে যাবো। ( l=mid_2+1 সেট করতে হবে)
    6. নয়তো আমরা নিশ্চিত যে x কে আমরা mid_1 থেকে mid_2 এই রেঞ্জেই খুঁজে পাবো। তাই আমরা মাঝেই থাকবো। ( l=mid_1 +1 এবং r=mid_2-1 ) সেট করতে হবে)
    7. পুনরায় ৩ নং এ যাই।

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

টারনারি সার্চ কিভাবে কাজ করে?

আমরা এখন টারনারি সার্চ কিভাবে কাজ করে তার একটি কমপ্লিট ভিজুয়ালাইজেশন দেখবো। ধরা যাক n=10 একটি অ্যারেতে আমদের একটি সংখ্যা x=22 খুঁজতে বলা হয়েছে। আমরা নিচের মতো করে অগ্রসর হবো।

Ternary search example

আমরা একটি অ্যারে নিবো যেখানে এলিমেন্ট হিসেবে ১,৪,৭,৯,২০,২২,৩৩,২৪,৪৫,৪৭ এই গুলো রাখা আছে এবং যার সাইজ n=10। আমরা অ্যারেটিকে আগেই সর্ট করে নিয়েছি। তারপর আমরা পরের ধাপে যাবো।

Ternary search step 1

এখানে আমরা দেখতে পাচ্ছি l=0 এবং r=9, যা আমাদের শর্ত l\leq r পূরণ করে। তাই আমরা সূত্র মোতাবেক mid_1 এবং mid_2 এর মান বের করবো।

mid_1 = l+ \lfloor \frac{ r-l }{3} \rfloor = 3
mid_2 = r – \lfloor \frac{ r-l }{3} \rfloor = 6

এখানে mid_1,mid_2 কনটাই আমাদের টার্গেট x=22 এর সমান নয়।

যেহেতু x=22 , ৯ থেকে বড় এবং ৩৩ থেকে ছোট তাই আমাদের পরবর্তী সার্চ রেঞ্জ হবে l=mid_1+1=4 এবং r=mid_2-1=5 .

Ternary search algorithm 2

এই ধাপটিও আমাদের শর্ত l\leq r পূরণ করে। তাই, আমরা ১ নং ধাপের মতো করে mid_1 এবং mid_2 এর মান হিসেব করবো। তারপর আমরা দেখবো অ্যারের এই দুটি পয়েন্টে কি আমাদের টার্গেট এলিমেন্ট আছে কি না। যেহেতু আছে ( Array[mid_2]=x=22 ), তাই আমরা true রিটার্ন করেছি।

টারনারি সার্চ ইমপ্লিমেন্টেশন (Ternary search implementation) [C++]

টারনারি সার্চ ইমপ্লিমেন্ট করাও বাইনারি সার্চের মতোই সহজ, তাই আমরা আগের পোস্টের বাইনারি সার্চের কোডটাকেই একটু মডিফাই করছি।

এখানে ১৫ নং লাইনে চেক করেছি mid_1 অথবা mid_2 এই দুটি পয়েন্টের কনটাতে আমাদের target আছে কিনা। যদি থাকে তাহলে এখানেই প্রিন্ট করে দিয়েছি।

নয়তো আমরা টার্গেটের উপর এবং mid_1,mid_2 এর উপর ভিত্তি করে সিদ্ধান্ত নিয়েছি কোন দিকে যাবো। যেহেতু আমাদের অ্যারেটা সর্টেড অ্যারে, তাই টার্গেট যদি mid_1 এর এলিমেন্ট থেকে কম হয় তাহলে আমরা বামে যাবো। তাই r=mid_1-1 সেট করে দিয়েছি। যদি টার্গেট mid_2 এর এলিমেন্ট থেকে বড় হয় তবে আমরা তিন নম্বর অংশ বা ডানে যাবো। তাই l=mid_2+1 সেট করে দিয়েছি। নয়তো আমরা নিশ্চিত যে আমাদের এলিমেন্ট mid_1+1 থেকে mid_2-1 এর রেঞ্জে রয়েছে। তাই এক্ষেত্রে আমরা l=mid_1+1,r=mid_2-1 সেট করে দিয়েছি। অতবার পুনরায় লুপ চালিয়েছি।

টারনারি সার্চ অ্যালগরিদম এনালাইসিস

যেহেতু টারনারি সার্চ প্রতিবার আমাদের অ্যারেকে তিন ভাগে ভাগ করছে। তাই আমাদের সার্চের টাইম কমপ্লেক্সিটি হলো O(log n)

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

প্রথমেই টারনারি সার্চ বাইনারি সার্চের চেয়ে আস্তে চলে। আপাত দৃষ্টি তে টারনারি সার্চকে দ্রুত মনে হলেও বাস্তবে বাইনারি সার্চ বেশি দ্রুত। বাইনারি সার্চের বাজে কেসে সার্চ কমপ্লেক্সিটি T(n)=2C log_2(n)+O(1) । অপর দিলে টারনারি সার্চের সার্চ কমপ্লেক্সিটি T(n)=4C log_3(n)+O(1) । সুতরাং দেখা যাচ্ছে বাইনারি সার্চ, টারনারি সার্চ থেকে দ্রুত।

টারনারি সার্চ প্র্যাকটিস প্রবলেম:

টারনারি সার্চের এবং বাইনারি সার্চের কিছু আলাদা আলাদা আপ্লিকেশন আছে। আমরা পরবর্তি কোন লিখাতে আলোচনা করবো ইনশাল্লাহ। #Happy_Coding

আরও পরুন: বাইনারি হিপ (Binary Heap) বা প্রায়োরিটি কিউ (Priority Queue)

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button