Problem link ও উৎস
- **Original source:** CP-Algorithms — Ternary Search (numerical methods)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Medium
- **Pattern:** unimodal function-এর চূড়া/খাদ খোঁজা
- **Basic idea inherited from:** 091 (binary search)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা function `f(x)` দেওয়া, যেটা **unimodal** — মানে আগে শুধু **বাড়ে**, তারপর শুধু **কমে** (একটাই চূড়া; বা উল্টোটা — আগে কমে পরে বাড়ে, একটাই খাদ)। জিজ্ঞেস: চূড়ার (বা খাদের) `x` কোথায়, আর সেখানে `f`-এর মান কত?
উদাহরণ: `f(x) = -(x - 3)² + 5` — এটা একটা উল্টানো parabola, চূড়া `x = 3`-এ, সেখানে মান 5। ternary search খুঁজে বের করবে `x ≈ 3`।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে binary search-এর সাথে এর আত্মীয়তা বেশি স্পষ্ট লাগবে।
### Input ও output {#6-example-input-and-output}
```text
function domain চূড়া x মান
-----------------------------------------------------------
f(x) = -(x-3)² + 5 [0, 10] 3.0 5.0
f(x) = -(x-7)² + 100 (integer) [0, 20] 7 100
f(x) = -x² + 4x (=x(4-x)) [0, 10] 2.0 4.0
খাদ খুঁজতে (minimization):
g(x) = (x-3)² [0, 10] 3.0 0.0 (সাইন উল্টে দাও)
```
দুটো জিনিস খেয়াল করো: **float domain**-এ আমরা যথেষ্ট iteration চালিয়ে কাছাকাছি যাই (একদম নিখুঁত নয়, কিন্তু খুব কাছে); **integer domain**-এ range 2-3-এ নেমে এলে বাকিটা সরাসরি চেক করি।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পাহাড়ি রাস্তায় হাঁটছ ঘন কুয়াশায় — চূড়া দেখতে পাচ্ছ না, কিন্তু পায়ের নিচে উঁচু না নিচু সেটা টের পাও। চূড়া খুঁজতে তুমি দুটো জায়গায় (একটা একটু সামনে, একটা আরও সামনে) উচ্চতা মেপে নাও।
- সামনের বিন্দু যদি আরও সামনের বিন্দুর চেয়ে **নিচু** হয় → চূড়া আরও সামনে, পেছনটা বাদ।
- সামনের বিন্দু যদি **উঁচু** হয় → চূড়া পেরিয়ে গেছ, সামনেরটা বাদ।
দুটো মেপে এক-তৃতীয়াংশ রাস্তা ছেঁটে ফেলো; বারবার করলে চূড়ায় পৌঁছে যাবে। কিন্তু এটা তখনই কাজ করে যখন রাস্তায় **একটাই** চূড়া — দুটো টিলা থাকলে গুলিয়ে যাবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **binary search** (problem 091)-এর ভাই। binary search-এ থাকে monotonic (একটানা বাড়া/কমা) তথ্য, একটাই probe (`mid`) নিলেই কোন দিকে যাব বোঝা যায়। কিন্তু একটা পাহাড়ে monotonic কিছু নেই — বাঁ দিকে বাড়ছে, ডান দিকে কমছে। তাই **একটা** probe যথেষ্ট নয়; ternary search **দুটো** probe নেয় (`m1`, `m2`) এবং তাদের তুলনায় দিক ঠিক করে।
সম্পর্কটা মনে রাখো: binary search = monotonic yes/no-তে সীমানা খোঁজা; ternary search = unimodal ওঠা-নামায় চূড়া খোঁজা। দুটোই "অর্ধেক/তৃতীয়াংশ ফেলে দাও" পরিবারের।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **unimodality** — একটাই চূড়া থাকা। এমন function-এ একটা সুন্দর সম্পত্তি আছে: range-এর ভেতরে **দুটো** বিন্দু (`m1 < m2`) নিলে তাদের মান তুলনা করেই বলা যায় চূড়া কোন দিকে।
- `f(m1) < f(m2)` হলে চূড়া `m1`-এর **বাঁয়ে নেই** → বাঁ অংশ `[lo, m1]` ফেলে দাও।
- `f(m1) > f(m2)` হলে চূড়া `m2`-এর **ডানে নেই** → ডান অংশ `[m2, hi]` ফেলে দাও।
প্রতি ধাপে range-এর এক-তৃতীয়াংশ কাটা পড়ে — তাই নাম ternary (তিন-ভাগ) search।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সোজা: domain-টা ছোট ছোট ধাপে ভেঙে (sampling) প্রতিটা `x`-এ `f` মেপে সবচেয়ে বড়টা বাছো।
```python
def peak_brute(f, lo, hi, steps=100000):
best_x = lo
best_val = f(lo)
for i in range(steps + 1):
x = lo + (hi - lo) * i / steps # সমান ব্যবধানে নমুনা
v = f(x)
if v > best_val:
best_val, best_x = v, x
return best_x
```
এটা ঠিক কাজ করে যদি যথেষ্ট ঘন sampling করো — `f(x) = -(x-3)²+5`-এ চূড়া প্রায় 3-এ পাবে। কিন্তু নির্ভুলতা পুরোপুরি `steps`-এর উপর; নিখুঁত চূড়া পেতে অনেক sample লাগে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
Sampling-এ একটা দ্বন্দ্ব: নির্ভুলতা বাড়াতে চাইলে `steps` বাড়াতে হয় — কিন্তু খরচ সরাসরি `steps`-এর সাথে বাড়ে (linear)।
```text
চাই 1e-3 নির্ভুলতা -> range/steps ≈ 1e-3 -> steps ≈ (range)·1000
চাই 1e-9 নির্ভুলতা -> steps ≈ (range)·1e9 (অসম্ভব ধীর)
```
মানে precision-এর প্রতিটা অতিরিক্ত digit-এ খরচ 10 গুণ — `O(1/ε)`। অথচ ternary search প্রতি iteration-এ range ⅔ করে, তাই precision-এর সাথে খরচ বাড়ে শুধু `log(1/ε)` — পাহাড়-সমান পার্থক্য।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **unimodal হলে এক-তৃতীয়াংশ অংশ নিশ্চিতভাবে বাদ দেওয়া যায়।** Domain-এ দুটো probe `m1, m2` রাখো (range-কে তিন ভাগ করে); তাদের মান তুলনা করে এক দিকের তৃতীয়াংশ ফেলে দাও। প্রতি ধাপে range `× 2/3` হয়।
```text
শুরু range = R
k ধাপ পরে = R · (2/3)^k
```
মাত্র ~100 iteration-এ range এত ছোট হয়ে যায় যে চূড়া কার্যত নিখুঁত। Sampling-এর `O(1/ε)`-এর বদলে এটা `O(log(1/ε))`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **পাহাড়ে monotonic কিছু নেই, তাই একটা probe কম পড়ে — দুটো probe নাও, তাদের তুলনায় কোন দিকে চূড়া নিশ্চিতভাবে নেই সেটা ফেলে দাও।**
সবচেয়ে বড় ফাঁদ: function **unimodal না হলে** (দুটো চূড়া, বা সমতল অংশ) ternary search চুপচাপ ভুল চূড়ায় আটকে যাবে — কোনো error দেবে না। তাই code লেখার **আগে** unimodality-র যুক্তি দাও (concept-notes-এর common mistake #2)।
### ছবিতে বোঝা {#5-visual-explanation}
দুটো probe `m1`, `m2` দিয়ে কোন দিক ফেলব ঠিক করা:
```text
unimodal f: আগে ওঠে, পরে নামে — একটাই চূড়া
f(x) ^ * চূড়া
| / \
| m1* *m2
| / \
| / \
+----|----|----|----|----> x
lo m1 m2 hi
f(m1) < f(m2) -> চূড়া m1-এর বাঁয়ে নেই
বাঁ অংশ [lo, m1] ছেঁটে ফেলো, lo = m1
f(m1) > f(m2) -> চূড়া m2-এর ডানে নেই
ডান অংশ [m2, hi] ছেঁটে ফেলো, hi = m2
m1 = lo + (hi - lo)/3, m2 = hi - (hi - lo)/3
প্রতি ধাপে range × 2/3 — দ্রুত ছোট হয়
```
লক্ষ করো — দুই probe একে অন্যকে দেখে, তাই একটাই তুলনায় এক-তৃতীয়াংশ নিশ্চিত বাদ যায়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`f(x) = -(x-3)² + 5`, range `[0, 10]` — কয়েক ধাপ হাতে চালাই:
1. **শুরু:** `lo = 0`, `hi = 10`। `m1 = 0 + 10/3 ≈ 3.33`, `m2 = 10 − 10/3 ≈ 6.67`।
`f(3.33) ≈ 4.89`, `f(6.67) ≈ -8.44`। যেহেতু `f(m1) > f(m2)` → ডান বাদ, `hi = 6.67`।
2. **ধাপ 2:** `lo = 0`, `hi = 6.67`। `m1 ≈ 2.22`, `m2 ≈ 4.44`।
`f(2.22) ≈ 4.39`, `f(4.44) ≈ 2.93`। `f(m1) > f(m2)` → `hi = 4.44`।
3. **ধাপ 3:** `lo = 0`, `hi = 4.44`। `m1 ≈ 1.48`, `m2 ≈ 2.96`।
`f(1.48) ≈ 2.69`, `f(2.96) ≈ 4.999`। এবার `f(m1) < f(m2)` → বাঁ বাদ, `lo = 1.48`।
4. **চলতে থাকে:** range ধীরে ধীরে 3-এর চারপাশে ছোট হয়ে আসে।
5. **শেষ:** অনেক iteration পরে `(lo + hi)/2 ≈ 3.0` — চূড়া পাওয়া গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def ternary_search_max(f, lo, hi, iters=200):
"""unimodal (আগে ওঠে পরে নামে) f-এর চূড়ার x ফেরত দেয়, [lo, hi]-এ।"""
for _ in range(iters):
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
if f(m1) < f(m2):
lo = m1 # চূড়া m1-এর বাঁয়ে নেই
else:
hi = m2 # চূড়া m2-এর ডানে নেই
return (lo + hi) / 2
def ternary_search_int_max(f, lo, hi):
"""integer domain-এ unimodal f-এর চূড়ার x (পূর্ণসংখ্যা)।"""
while hi - lo > 2:
m1 = lo + (hi - lo) // 3
m2 = hi - (hi - lo) // 3
if f(m1) < f(m2):
lo = m1 + 1
else:
hi = m2 - 1
best = lo
for x in range(lo, hi + 1): # ছোট range সরাসরি চেক
if f(x) > f(best):
best = x
return best
# --- ছোট test গুলো (সব pass করা উচিত) ---
peak = ternary_search_max(lambda x: -(x - 3) ** 2 + 5, 0, 10)
assert abs(peak - 3.0) < 1e-4 # চূড়া x = 3
peak2 = ternary_search_max(lambda x: x * (4 - x), 0, 10) # -x²+4x, চূড়া 2
assert abs(peak2 - 2.0) < 1e-4
xi = ternary_search_int_max(lambda x: -(x - 7) ** 2 + 100, 0, 20)
assert xi == 7 # integer চূড়া 7
# minimization: সাইন উল্টে দিলেই খাদ খোঁজা
valley = ternary_search_max(lambda x: -((x - 3) ** 2), 0, 10)
assert abs(valley - 3.0) < 1e-4 # (x-3)²-এর খাদ x = 3
print(round(peak, 4)) # 3.0
print(round(peak2, 4)) # 2.0
print(xi) # 7
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
```
range-টাকে তিন সমান ভাগ করে দুটো ভেতরের বিন্দু বানাচ্ছি: `m1` এক-তৃতীয়াংশে, `m2` দুই-তৃতীয়াংশে।
```text
if f(m1) < f(m2):
lo = m1
else:
hi = m2
```
এটাই হৃদয়। `f(m1) < f(m2)` মানে `m1`-এর দিকটা নিচু — চূড়া ওদিকে নেই, তাই `lo` সরিয়ে দিই। নাহলে উল্টো — `hi` সরাই। হয় এক-তৃতীয়াংশ বাঁ, নয় এক-তৃতীয়াংশ ডান বাদ।
```text
return (lo + hi) / 2
```
অনেক iteration পরে `lo` আর `hi` চূড়ার গায়ে লেগে এসেছে; তাদের মাঝবিন্দুই উত্তর।
```text
while hi - lo > 2:
...
for x in range(lo, hi + 1):
```
integer version-এ range 2-এর বেশি থাকলে এক-তৃতীয়াংশ কাটি; 2-3-এ নেমে এলে বাকি কয়টা মান সরাসরি চেক করি (float-এর মতো অসীম ভাগ করা যায় না বলে)।
বাকি `assert` গুলো নিজেদের যাচাই করছে — পরিচিত function-গুলোর চূড়া জানা মানের সাথে মিলছে কিনা। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
3.0
2.0
7
সব test pass!
```
প্রথম লাইন `-(x-3)²+5`-এর চূড়া → 3.0; দ্বিতীয় `x(4-x)`-এর চূড়া → 2.0; তৃতীয় integer function-এর চূড়া → 7। তার আগের `assert` গুলো চুপচাপ pass করেছে (float-এ `< 1e-4` সহনশীলতায়, integer-এ ঠিক সমান)। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log(1/ε))** — float-এ যেখানে `ε` চাই precision। প্রতি iteration-এ range `× 2/3`, তাই `n` ধাপ পরে range `R · (2/3)^n`; কাঙ্ক্ষিত precision পেতে `n ≈ log(R/ε) / log(1.5)`। সাথে প্রতি ধাপে `f` দুবার মাপার খরচ গুণ হবে। integer-এ `O(log(range))`।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `lo`, `hi`, `m1`, `m2` — গুটিকয় variable। range-টা শুধু সংকুচিত হয়, কোনো বাড়তি list/array লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Non-unimodal function-এ চালানো** — দুটো চূড়া থাকলে ternary search ভুল চূড়ায় আটকাবে, error দেবে না; আগে unimodality প্রমাণ করো (concept-notes mistake #2)।
2. **খুব কম iteration** — float-এ 20-30 iteration-এ precision কম; 100-200 নিরাপদ (খরচ সামান্য, কারণ log)।
3. **Integer-এ ভাগ-অবধি ভুল** — `hi - lo` 2-এর নিচে না নামিয়ে loop চালালে infinite loop বা off-by-one; ছোট range সরাসরি চেক করা নিরাপদ।
4. **Minimization-এ সাইন ভুলে যাওয়া** — চূড়ার code দিয়ে খাদ খুঁজতে `-f(x)` দিতে হয়; নাহলে উল্টো উত্তর।
5. **m1, m2 ভুল সাইডে আপডেট** — `f(m1) < f(m2)`-এ `lo = m1` (চূড়া ডানে); উল্টে ফেললে চূড়া হারাবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **Codeforces — Devu and his Brother** (