Binary search — duplicate-এর দুই সীমা¶
- Original source: এই repository-র নিজস্ব অনুশীলন
- Topic: sorting / searching
- Difficulty: Easy
- Pattern: lower bound / upper bound
- Course: Microsoft · Module 2-এর topic অনুশীলন; official assignment নয়
প্রশ্ন ও উদাহরণ¶
একটি sorted integer list ও target দেওয়া আছে। সমান মানের শুরু ও শেষের পরের index বের করুন। Empty input ও duplicate থাকতে পারে। হাতে trace করার সময় সর্বোচ্চ 8টি মান নিন; lab report-এ সর্বোচ্চ 200টি product।
- Input:
[1, 2, 2, 2, 5], target = 2 - Output:
lower = 1, upper = 4; range [1, 4)
ভিত্তির ধারণা¶
আগে পড়ুন: sorting/searching-এর ধারণা, array ও index। এরপর lower bound / upper bound-এর কাজটি নিজের ভাষায় বলুন।
Sorted array-তে target-এর চেয়ে ছোট অংশকে lower bound-এর বাঁয়ে রাখুন। Upper bound খুঁজতে target-এর সমান অংশও বাঁয়ে রাখুন। এতে duplicate-এর পুরো অংশ [lower, upper) পাওয়া যায়।
ধাপে ধাপে সমাধান¶
| Lower bound-এর ধাপ | low | high | mid | সিদ্ধান্ত |
|---|---|---|---|---|
| শুরু | 0 | 5 | 2 | value 2 → high = 2 |
| পরের ধাপ | 0 | 2 | 1 | value 2 → high = 1 |
| শেষ তুলনা | 0 | 1 | 0 | value 1 → low = 1 |
| থামা | 1 | 1 | — | lower = 1 |
Checkpoint: পরের তুলনা code চালানোর আগে নিজে লিখুন। কোন অংশ আর বদলাবে না, সেটি চিহ্নিত করুন।
ইঙ্গিত: Target না থাকলে lower == upper। খালি array-তে দুটিই 0। Sorted input ছাড়া binary search চালাবেন না।
কোড ও ব্যাখ্যা¶
সম্পূর্ণ implementation আছে sorting_lab.py-এ। Repository root থেকে নিচের ছোট example চালানো যায়:
from practice.sorting_lab import lower_bound, upper_bound
a = [1, 2, 2, 2, 5]
print(lower_bound(a, 2), upper_bound(a, 2)) # 1 4
প্রথমে reference না দেখে function লিখুন। পরে loop boundary ও কোন অবস্থায় pointer বাড়ছে তা reference-এর সঙ্গে মিলিয়ে দেখুন।
খরচ ও সাধারণ ভুল¶
প্রতি boundary query O(log n) time ও O(1) extra space; matching item বের করতে অতিরিক্ত O(k)।
Empty list, একই মান বারবার, আগে থেকেই sorted, উল্টো sorted এবং একটিমাত্র element পরীক্ষা করুন। Input list ভুল করে বদলে যাচ্ছে কি না তাও দেখুন।
শেখা ও পরের অনুশীলন¶
পরীক্ষাগুলো দিয়ে output, stability ও edge case মিলিয়ে নিন:
তারপর পণ্যের catalogue guided challenge-এ একই algorithm বাস্তব query-র সঙ্গে ব্যবহার করুন। তালিকায় ফিরুন।