Problem link ও উৎস
- **Original source:** Classic exercise (Python-এর `bisect.bisect_right`-এর হাতে-বানানো রূপ)
- **Platform:** — (standard library concept; related: Python docs —
)
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Easy
- **Pattern:** first > x (প্রথম যেখানে `a[i] > x`)
- **Basic idea inherited from:** 092 — Lower Bound
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** array `a` আর একটা সংখ্যা `x`। বলতে হবে — **সবচেয়ে ছোট index `i`** যেখানে `a[i] > x` (কড়াকড়ি বড়, সমান না)। অর্থাৎ x-এর সব occurrence পেরিয়ে ঠিক পরের জায়গা।
আরেকভাবে: x-কে array-তে ঢোকালে, **ডান দিক ঘেঁষে** (একই মানের সবার পরে) সে কোন index-এ বসবে — সেটাই upper bound।
092-এর সাথে পার্থক্য: lower bound x-এর **প্রথম** সমান-বা-বড়ে আঙুল রাখে; upper bound x-এর **সব সমান পেরিয়ে** প্রথম কড়া-বড়ে। x না থাকলে দুটো একই উত্তর দেয়।
### Input ও output {#6-example-input-and-output}
```text
a (sorted) x -> upper bound (ব্যাখ্যা)
-----------------------------------------------------
[1, 3, 3, 3, 7] 3 -> 4 (সব 3 পেরিয়ে, 7-এর index)
[1, 3, 3, 3, 7] 4 -> 4 (4 নেই; lower==upper)
[1, 3, 3, 3, 7] 7 -> 5 (সব 7 পেরিয়ে = len)
[1, 3, 3, 3, 7] 0 -> 0 (সবার চেয়ে ছোট; শুরুতে)
[1, 3, 3, 3, 7] 8 -> 5 (সবার চেয়ে বড় = len)
[] 5 -> 0 (খালি array)
```
খেয়াল করো: x = 7 (সবচেয়ে বড় element)-এ upper bound = 5 = `len(a)`, কারণ 7-এর চেয়ে কড়া-বড় কিছুই নেই — সব পেরিয়ে শেষের পরে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
আবার লাইব্রেরির সেই sorted তাক, একই number `x`-এর কয়েকটা বই পাশাপাশি রাখা। 092-তে নতুন বই বসাতাম এই দলটার ঠিক **আগে** (বাঁয়ে)।
এবার তুমি বসাও দলটার ঠিক **পরে** (ডানে) — সব x পেরিয়ে। যদি x-এর কোনো বই না থাকে, "আগে" আর "পরে" একই জায়গা — তখন lower আর upper bound মিলে যায়। কিন্তু x-এর তিনটা বই থাকলে দুটোর মাঝে ঠিক তিন ঘরের ফাঁক — সেই ফাঁকই গুনে বলে দেয় কয়টা x আছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
092 (Lower Bound)-এর কাঠামো এখানে **হুবহু** — `while lo < hi`, `hi = mid`, `lo = mid + 1`, `hi = len(a)` দিয়ে শুরু। একটাই লাইন বদলায়:
- 092: `if a[mid] < x` (শর্ত `>= x`-এর জন্য)
- 093: `if a[mid] <= x` (শর্ত `> x`-এর জন্য)
ব্যস, ওই একটা `=` যোগ হওয়াই lower bound-কে upper bound বানিয়ে দেয়। এত কাছাকাছি বলেই দুটো একসাথে শেখা উচিত — তাহলে আর গুলোবে না।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
আবার সেই **monotonic শর্তে binary search** — শুধু শর্তটা এবার `a[i] > x`। এটাও একবার সত্যি হলে ডান দিকে সব সত্যি, তাই সিঁড়ি **F F F T T T**, আর প্রথম T-টাই উত্তর।
বড় idea: lower bound (`>= x`) আর upper bound (`> x`)-এর **ফারাকটাই বলে দেয় x array-তে কয়বার আছে** — কারণ মাঝের সব index-এর element ঠিক x।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে `a[i] > x` পেলে সেই index:
```python
def upper_bound_brute(a, x):
for i in range(len(a)):
if a[i] > x:
return i
return len(a) # কেউ > x না — শেষের পরে
```
092-এর brute force-এর সাথে একটাই পার্থক্য: শর্তে `>=` নয়, `>`। বাকি সব এক — `return len(a)` লাইনটাও একই কারণে দরকার (x সবার চেয়ে বড়/সমান হলে)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সেই একই কথা — সবচেয়ে খারাপ ক্ষেত্রে পুরো array, **O(n)**। sorted তথ্য কাজে লাগে না।
```text
n = 1,000,000 হলে:
linear scan : ~1,000,000 তুলনা (O(n))
binary search : ~20 তুলনা (O(log n))
```
আর "x কয়বার আছে" বের করতে যদি lower + upper দুটোই linear-এ করো, সেটা O(n) — অথচ দুটো binary search মিলে O(log n)।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
শর্ত `a[i] > x`-এর সিঁড়ি **F F F T T T** — monotonic। প্রথম T খুঁজি binary search-এ, ঠিক 092-এর মতো, শুধু তুলনায় `<=`:
```python
def upper_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= x:
lo = mid + 1 # mid এখনো F (a[mid] ≤ x) — বাঁ অর্ধেক বাদ
else:
hi = mid # mid হয়তো প্রথম T (a[mid] > x) — রেখে দাও
return lo
```
প্রতি ধাপে অর্ধেক → O(log n)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল মোচড়: **`<` কে `<=` বানালেই lower bound হয়ে যায় upper bound।** কারণ `a[mid] == x` ক্ষেত্রটা কোন দিকে যায়, সেটাই ঠিক করে আমরা x-এর বাঁয়ে থামছি না ডানে।
- 092-এ `a[mid] == x` হলে শর্ত (`< x`) মিথ্যা → `hi = mid` → x-এর দিকে চেপে থামি → **বাঁ** bound।
- 093-এ `a[mid] == x` হলে শর্ত (`<= x`) সত্যি → `lo = mid + 1` → x পেরিয়ে যাই → **ডান** bound।
এই এক অক্ষরের (`=`) পার্থক্যেই duplicate-এ দুই দিকের সীমানা। আর `upper - lower = count` — এই সম্পর্কটা মনে গেঁথে নাও, গোনা-জাতীয় বহু problem-এ লাগবে (102-এও এর আত্মীয়)।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 3, 3, 3, 7], x = 3`। শর্ত এবার "`a[i] > 3`?":
```text
a = [ 1 3 3 3 7 ]
index = 0 1 2 3 4 5 (শেষের পরে)
a[i]>3 = F F F F T
↑
প্রথম T → upper bound = 4
lower bound (092, প্রথম ≥3) = 1
upper bound (এখানে, প্রথম >3) = 4
ফারাক = 4 - 1 = 3 → 3 আছে ঠিক 3 বার!
```
দুটো bound-এর মাঝের সব ঘরে (index 1, 2, 3) বসে আছে ঠিক x = 3। তাই ফারাক = গণনা।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 3, 3, 3, 7], x = 3` চালাই (`hi = 5`):
| step | lo | hi | mid | a[mid] | a[mid] <= 3? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 0 | 5 | 2 | 3 | হ্যাঁ | lo = mid + 1 = 3 |
| 2 | 3 | 5 | 4 | 7 | না | hi = mid = 4 |
| 3 | 3 | 4 | 3 | 3 | হ্যাঁ | lo = mid + 1 = 4 |
| — | 4 | 4 | — | — | — | lo == hi → return 4 |
উত্তর 4 — সব 3 পেরিয়ে 7-এর index। তুলনা করো 092-এর dry run-এর সাথে (একই array, একই x, কিন্তু উত্তর 1) — পুরো পার্থক্যটা ওই `<` বনাম `<=`।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def upper_bound(a, x):
"""sorted a-তে প্রথম index যেখানে a[i] > x; কেউ না থাকলে len(a)।"""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= x:
lo = mid + 1 # mid এখনো ≤ x — বাঁ অর্ধেক বাদ
else:
hi = mid # mid > x, হয়তো প্রথম T — রেখে দাও
return lo
def lower_bound(a, x): # 092 থেকে, count বের করতে লাগবে
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def count_of(a, x):
"""x array-তে কয়বার আছে = upper - lower।"""
return upper_bound(a, x) - lower_bound(a, x)
from bisect import bisect_right
def upper_bound_brute(a, x):
for i in range(len(a)):
if a[i] > x:
return i
return len(a)
# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [1, 3, 3, 3, 7]
assert upper_bound(a, 3) == 4 # সব 3 পেরিয়ে
assert upper_bound(a, 4) == 4 # 4 নেই
assert upper_bound(a, 7) == 5 # সব 7 পেরিয়ে = len
assert upper_bound(a, 0) == 0 # সবচেয়ে ছোট
assert upper_bound(a, 8) == 5 # সবচেয়ে বড় = len
assert upper_bound([], 5) == 0 # খালি array
# upper - lower = count যাচাই
assert count_of(a, 3) == 3 # 3 আছে 3 বার
assert count_of(a, 7) == 1 # 7 আছে 1 বার
assert count_of(a, 4) == 0 # 4 নেই
# bisect_right আর brute force-এর সাথে মিলিয়ে দেখি
big = [0, 2, 2, 4, 4, 4, 6, 9, 9, 10]
for x in range(-2, 13):
assert upper_bound(big, x) == bisect_right(big, x)
assert upper_bound(big, x) == upper_bound_brute(big, x)
print(upper_bound(a, 3)) # 4
print(count_of(a, 3)) # 3
print(upper_bound(a, 7)) # 5
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
lo, hi = 0, len(a)
```
092-এর মতোই range `[0, len(a)]` — কারণ উত্তর `len(a)`-ও হতে পারে (x সবার চেয়ে বড় হলে)।
```text
if a[mid] <= x: lo = mid + 1
```
এটাই একমাত্র পার্থক্য 092-এর সাথে। `a[mid] <= x` মানে mid এখনো শর্ত (`> x`) পূরণ করে না — তাই mid সহ বাঁ অর্ধেক বাদ। লক্ষ করো `a[mid] == x` ক্ষেত্রটাও এখানে পড়ে, তাই x-এর সমান ঘরগুলো পেরিয়ে যাই (ডান bound)।
```text
else: hi = mid
```
`a[mid] > x` — mid নিজেই হয়তো প্রথম T। রেখে দিই।
```text
return upper_bound(a, x) - lower_bound(a, x)
```
`count_of`-এর হৃদয়: দুই bound-এর ফারাকই x-এর গণনা — মাঝের সব ঘরে ঠিক x বসে আছে।
cross-check-এ `bisect_right` আর brute force দুটোর সাথে, এবং count সম্পর্ক — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
3
5
সব test pass!
```
প্রথম: `upper_bound(a, 3)` = 4 (সব 3 পেরিয়ে)। দ্বিতীয়: `count_of(a, 3)` = 3 (upper 4 − lower 1)। তৃতীয়: `upper_bound(a, 7)` = 5 (সব 7 পেরিয়ে = len)। আগের সব `assert` (bisect_right, brute force, count যাচাই সহ) চুপচাপ pass। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — প্রতি ধাপে অর্ধেক, ঠিক 092-এর মতো। "x কয়বার আছে" বের করতে দুটো বার (lower + upper) চালালেও মোট O(log n)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `lo`, `hi`, `mid`; বাড়তি array লাগে না। (test-এর `big` list আলাদা।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`<` আর `<=` অদলবদল** — সবচেয়ে কমন। lower bound-এ `<`, upper bound-এ `<=`। ভুল করলে duplicate-এ এক ঘর এদিক-ওদিক — কিন্তু x না থাকলে দুটোই একই দেয়, তাই bug চাপা পড়ে যায়।
2. **count বের করতে `upper - lower + 1` লেখা** — না, ফারাকটাই সরাসরি count, `+1` লাগে না (half-open interval)।
3. **`hi = len(a) - 1` দিয়ে শুরু** — x সবচেয়ে বড় হলে উত্তর `len(a)` মিস হয়; range `[0, len(a)]` রাখো।
4. **`while lo <= hi` লেখা** — `hi = mid` থাকায় infinite loop। এই template-এ `while lo < hi`।
5. **bisect_left আর bisect_right মনে রাখায় ভুল** — `bisect_left` = lower (প্রথম ≥), `bisect_right` = upper (প্রথম >)। নাম থেকে ধরো: "left" = বাঁ ঘেঁষে = ≥; "right" = ডান ঘেঁষে = >।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Find First and Last Position** (