সার্চিং অ্যালগরিদমের মধ্যে রিকার্সিভ বাইনারী সার্চ অন্যতম। এটা মূলত বাইনারি সার্চ অ্যালগরিদম। সাধারন বাইনারি সার্চ অ্যালগরিদমের সাথে এইটার পার্থক্য হল, এই অ্যালগরিদমটা রিকার্সনের মাধ্যমে কাজ করে। এই পোষ্টে আমরা শিখব কিভাবে রিকার্সিভ বাইনারী সার্চ অ্যালগরিদম কাজ করে। রিকার্সিভ বাইনারী সার্চ অ্যালগরিদমটা মূলত এই রকমঃ
Binary_search(a, i, l, x)
{
if(l == i)
{
if(x == a[i])
{
return i;
}
else
{
return 0;
}
}
else
{
mid := i+l/2;
if(x == a[mid])
{
return mid;
}
else if(x < a[mid])
{
return Binary_search(a, i, mid - 1, x);
}
else
{
return Binary_search(a, mid + 1, l, x);
}
}
}
রিকার্সিভ বাইনারি সার্চ কিভাবে কাজ ক?
ধর, আমাদের কাছে n সংখ্যক এলিমেন্ট আছে…
যখন n = 1, তখন start ভ্যারিয়েবলের ভ্যালু হবে 1 এবং end ভ্যারিয়েবলের ভ্যালু হবে 1. সেক্ষেত্রে start = end হয়। যখন আমরা ফাংশনটা কল করব তখন অ্যালগরিদমের if কন্ডিশন কাজ করবে। n = 1 হবার কারনে অ্যারে তে শুধুমাত্র একটা এলিমেন্ট থাকবে।
আমরা যেই আইটেমটা সার্চ সেটা যদি ঐ অ্যারে এলিমেন্টের সাথে মিলে যায় তাহলে সার্চ আইটেমটার লোকেশনের জন্য start ভ্যারিয়েবলের ভ্যলু রিটার্ন করবে। আর যদি আমরা যেই আইটেমটা সার্চ সেটা ঐ অ্যারে এলিমেন্টের সাথে না মিলে তাহলে সার্চ আইটেমটার লোকেশন 0 (শূন্য) রিটার্ন করবে।
এবার যদি n > 1 হয় তাহলে অ্যালগরিদমের else কন্ডিশনটা কাজ করবে। সেক্ষেত্রে আমাদের কাছে চারটা অপশন থাকবে।
১) সার্চ আইটেমটার লোকেশন mid পজিশনে থাকবে – সেক্ষেত্রে অ্যালগরিদমের else কন্ডিশনের if loop টা কল হবে এবং সার্চ আইটেমটার লোকেশনের জন্য mid ভ্যারিয়েবলের ভ্যালু রিটার্ন করবে।
২) সার্চ আইটেমটার লোকেশন mid পজিশন থেকে কম হবে– সেক্ষেত্রে অ্যালগরিদমের else কন্ডিশনের else if loop টা কল হবে। যতক্ষন সার্চ আইটেমটা পাবে না ততক্ষন ফাংশনটা কল করবে এবং প্রতিবার ফাংশন কল করার সময় mid ভ্যারিয়েবলের ভ্যালু 1 করে কমবে। যখন সার্চ আইটেমটা অ্যারে এলিমেন্ট লিস্টে পাবে তখন সার্চ আইটেমটার লোকেশনের জন্য mid ভ্যারিয়েবলের ভ্যালু রিটার্ন করবে (এক্ষেত্রে mid ভ্যারিয়েবলের ভ্যালু প্রথমে যা ছিল তা থাকবে না কারন প্রতিবার ফাংশন কল করার জন্য mid ভ্যারিয়েবলের ভ্যালু 1 করে কমে যাচ্ছে) আর যদি সার্চ আইটেমটা না পায় তাহলে সার্চ আইটেমটার লোকেশন 0 (শূন্য) রিটার্ন করবে।
৩) সার্চ আইটেমটার লোকেশন mid পজিশন থেকে বেশী হবে– সেক্ষেত্রে অ্যালগরিদমের else কন্ডিশনের else loop টা কল হবে। যতক্ষন সার্চ আইটেমটা পাবে না ততক্ষন ফাংশনটা কল করবে এবং প্রতিবার ফাংশন কল করার সময় mid ভ্যারিয়েবলের ভ্যালু 1 করে বাড়বে। যখন সার্চ আইটেমটা অ্যারে এলিমেন্ট লিস্টে পাবে তখন সার্চ আইটেমটার লোকেশনের জন্য mid ভ্যারিয়েবলের ভ্যালু রিটার্ন করবে (এক্ষেত্রে mid ভ্যারিয়েবলের ভ্যালু প্রথমে যা ছিল তা থাকবে না কারন প্রতিবার ফাংশন কল করার জন্য mid ভ্যারিয়েবলের ভ্যালু 1 করে বেড়ে যাচ্ছে), আর যদি সার্চ আইটেমটা না পায় তাহলে সার্চ আইটেমটার লোকেশন 0 (শূন্য) রিটার্ন করবে।
৪) সার্চ আইটেমটা ঐই অ্যারে এলিমেন্টগুলোর মধ্যে নেই – সার্চ আইটেমটা যদি অ্যারে তে না পায় তাহলে সার্চ আইটেমটার লোকেশন 0 (শূন্য) রিটার্ন করবে। এটা মূলত ২ নাম্বার এবং ৩ নাম্বার অপশনের রেজাল্ট।
আশাকরি আমরা রিকার্সিভ বাইনারী সার্চ কিভাবে কাজ করে তা বুঝতে পেরেছি।
শিমুলের ব্লগ 
1 thoughts on “রিকার্সিভ বাইনারী সার্চ”