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

নির্দেশনা

আপনার কাজ হলো একটি বাইনারি সার্চ অ্যালগরিদম বাস্তবায়ন করা।

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

অ্যালগরিদমটি দেখতে এমন:

• একটি সাজানো অ্যারের মাঝের এলিমেন্ট খুঁজে বের করুন এবং সেটির সাথে আমাদের খোঁজা আইটেমের তুলনা করুন।
• যদি মাঝের এলিমেন্টটি হয় আমাদের খোঁজা আইটেম, তাহলে আমাদের কাজ শেষ!
• যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে বড় হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার পরের সব এলিমেন্ট বাদ দিতে পারি।
• যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে ছোট হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার আগের সব এলিমেন্ট বাদ দিতে পারি।
• যদি অ্যারের প্রতিটি এলিমেন্ট বাদ দেওয়া হয়ে যায়, তাহলে আইটেমটি অ্যারেতে নেই।
• অন্যথায়, অ্যারের যে অংশটি এখনো বাদ দেওয়া হয়নি তার উপর একই প্রক্রিয়া পুনরাবৃত্তি করুন।

এখানে একটি উদাহরণ:

ধরা যাক, আমরা নিচের সাজানো অ্যারেতে 23 সংখ্যাটি খুঁজছি: [4, 8, 12, 16, 23, 28, 32].

• আমরা প্রথমে 23-কে মাঝের এলিমেন্ট 16-এর সাথে তুলনা করি।
• যেহেতু 23, 16-এর চেয়ে বড়, তাই আমরা অ্যারের বাম অর্ধেক বাদ দিতে পারি, ফলে আমাদের হাতে থাকে [23, 28, 32].
• এরপর আমরা 23-কে নতুন মাঝের এলিমেন্ট 28-এর সাথে তুলনা করি।
• যেহেতু 23, 28-এর চেয়ে ছোট, তাই আমরা অ্যারের ডান অর্ধেক বাদ দিতে পারি: [23].
• আমরা আমাদের আইটেমটি খুঁজে পেয়েছি।

আচরণ

পরীক্ষার কেসগুলোতে আপনার সমাধানের আচরণ Julia-র বিল্ট-ইন searchsorted ফাংশনগুলোর আচরণের সাথে মিলতে হবে। এর মানে হলো, অ্যারেতে পাওয়া প্রথম মিলে যাওয়া এলিমেন্টের ইনডেক্স রিটার্ন করার বদলে আপনি একটি রেঞ্জ রিটার্ন করবেন, যার নিম্নসীমা হবে অ্যারেতে প্রথম মিলে যাওয়া এলিমেন্টের ইনডেক্স এবং ঊর্ধ্বসীমা হবে অ্যারেতে শেষ মিলে যাওয়া এলিমেন্টের ইনডেক্স। তবে, আপনার সমাধান সহজ করতে আপনি ধরে নিতে পারেন যে লক্ষ্য এলিমেন্টটি পুনরাবৃত্ত হয় না, একাধিক মিলের বোনাস কাজের টেস্টসেটটি ছাড়া।

খোঁজা আইটেমটি যদি অ্যারেতে না থাকে, তাহলে আপনাকে একটি খালি রেঞ্জ রিটার্ন করতে হবে, যার নিম্নসীমা হবে সেই ইনডেক্স যেখানে আইটেমটি সাজানো অ্যারেতে ঢোকানো যেত। খালি রেঞ্জ বলতে এমন যেকোনো রেঞ্জকে বোঝায় যেখানে ঊর্ধ্বসীমা নিম্নসীমার চেয়ে কম।

আরও বিস্তারিত জানতে searchsorted ফাংশনের ডকুমেন্টেশন ও উদাহরণগুলো পড়ুন:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

বোনাস কাজ

• আপনার সমাধানটি বাড়িয়ে by, lt ও rev কিওয়ার্ড আর্গুমেন্টগুলো সমর্থন করান, যাতে by অ্যারের সব এলিমেন্টে প্রয়োগ করা একটি রূপান্তর নির্দিষ্ট করে, lt একটি তুলনা নির্দিষ্ট করে এবং rev নির্দিষ্ট করে অ্যারেটি উল্টো ক্রমে সাজানো কি না। এই প্যারামিটারগুলো ব্যবহার করা হলে আপনাকে ধরে নিতে হবে যে অ্যারেটি ইতিমধ্যে এই প্যারামিটারগুলো দিয়েই সাজানো হয়েছে। আরও বিস্তারিত জানতে sort-এর ডকুমেন্টেশন দেখুন।
• এমন অ্যারে সমর্থন করুন যেখানে লক্ষ্য এলিমেন্টটি পুনরাবৃত্ত (লক্ষ্য এলিমেন্টের সাথে সমান হিসেবে মেলে এমন প্রথম ও শেষ ইনডেক্স খুঁজে বের করুন)।

---

সূত্র

Wikipedia