140 — Ternary Search¶

Binary search-এর একটা মজার ভাই — ternary search। Binary search খোঁজে sorted জিনিসে "এই মানটা কোথায়"; ternary search খোঁজে একটা পাহাড়ের চূড়া (বা খাদের তলা)। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী) — তাই চাপহীন মনে এই সুন্দর কৌশলটা উপভোগ করো।

Source¶

Original source: CP-Algorithms — Ternary Search (numerical methods)
Platform: CP-Algorithms — https://cp-algorithms.com/num_methods/ternary_search.html
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Medium
Pattern: unimodal function-এর চূড়া/খাদ খোঁজা
Basic idea inherited from: 091 (binary search)

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-এর সাথে এর আত্মীয়তা বেশি স্পষ্ট লাগবে।

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।

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 ওঠা-নামায় চূড়া খোঁজা। দুটোই "অর্ধেক/তৃতীয়াংশ ফেলে দাও" পরিবারের।

4. Real-life analogy¶

ভাবো একটা পাহাড়ি রাস্তায় হাঁটছ ঘন কুয়াশায় — চূড়া দেখতে পাচ্ছ না, কিন্তু পায়ের নিচে উঁচু না নিচু সেটা টের পাও। চূড়া খুঁজতে তুমি দুটো জায়গায় (একটা একটু সামনে, একটা আরও সামনে) উচ্চতা মেপে নাও।

সামনের বিন্দু যদি আরও সামনের বিন্দুর চেয়ে নিচু হয় → চূড়া আরও সামনে, পেছনটা বাদ।
সামনের বিন্দু যদি উঁচু হয় → চূড়া পেরিয়ে গেছ, সামনেরটা বাদ।

দুটো মেপে এক-তৃতীয়াংশ রাস্তা ছেঁটে ফেলো; বারবার করলে চূড়ায় পৌঁছে যাবে। কিন্তু এটা তখনই কাজ করে যখন রাস্তায় একটাই চূড়া — দুটো টিলা থাকলে গুলিয়ে যাবে।

5. Visual explanation¶

দুটো probe m1, m2 দিয়ে কোন দিক ফেলব ঠিক করা:

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 একে অন্যকে দেখে, তাই একটাই তুলনায় এক-তৃতীয়াংশ নিশ্চিত বাদ যায়।

6. Example input and output¶

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-এ নেমে এলে বাকিটা সরাসরি চেক করি।

7. Brute force thinking¶

সবচেয়ে সোজা: domain-টা ছোট ছোট ধাপে ভেঙে (sampling) প্রতিটা x-এ f মেপে সবচেয়ে বড়টা বাছো।

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)।

চাই 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 হয়।

শুরু 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)।

11. Step-by-step dry run¶

f(x) = -(x-3)² + 5, range [0, 10] — কয়েক ধাপ হাতে চালাই:

শুরু: 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: 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: 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।
চলতে থাকে: range ধীরে ধীরে 3-এর চারপাশে ছোট হয়ে আসে।
শেষ: অনেক iteration পরে (lo + hi)/2 ≈ 3.0 — চূড়া পাওয়া গেল।

12. Python solution¶

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¶

        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3

range-টাকে তিন সমান ভাগ করে দুটো ভেতরের বিন্দু বানাচ্ছি: m1 এক-তৃতীয়াংশে, m2 দুই-তৃতীয়াংশে।

        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2

এটাই হৃদয়। f(m1) < f(m2) মানে m1-এর দিকটা নিচু — চূড়া ওদিকে নেই, তাই lo সরিয়ে দিই। নাহলে উল্টো — hi সরাই। হয় এক-তৃতীয়াংশ বাঁ, নয় এক-তৃতীয়াংশ ডান বাদ।

    return (lo + hi) / 2

অনেক iteration পরে lo আর hi চূড়ার গায়ে লেগে এসেছে; তাদের মাঝবিন্দুই উত্তর।

    while hi - lo > 2:
        ...
    for x in range(lo, hi + 1):

integer version-এ range 2-এর বেশি থাকলে এক-তৃতীয়াংশ কাটি; 2-3-এ নেমে এলে বাকি কয়টা মান সরাসরি চেক করি (float-এর মতো অসীম ভাগ করা যায় না বলে)।

বাকি assert গুলো নিজেদের যাচাই করছে — পরিচিত function-গুলোর চূড়া জানা মানের সাথে মিলছে কিনা। সব মিললে শেষে সব test pass!।

14. Output walkthrough¶

চালালে ছাপবে:

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!।

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¶

Non-unimodal function-এ চালানো — দুটো চূড়া থাকলে ternary search ভুল চূড়ায় আটকাবে, error দেবে না; আগে unimodality প্রমাণ করো (concept-notes mistake #2)।
খুব কম iteration — float-এ 20-30 iteration-এ precision কম; 100-200 নিরাপদ (খরচ সামান্য, কারণ log)।
Integer-এ ভাগ-অবধি ভুল — hi - lo 2-এর নিচে না নামিয়ে loop চালালে infinite loop বা off-by-one; ছোট range সরাসরি চেক করা নিরাপদ।
Minimization-এ সাইন ভুলে যাওয়া — চূড়ার code দিয়ে খাদ খুঁজতে -f(x) দিতে হয়; নাহলে উল্টো উত্তর।
m1, m2 ভুল সাইডে আপডেট — f(m1) < f(m2)-এ lo = m1 (চূড়া ডানে); উল্টে ফেললে চূড়া হারাবে।

18. Harder problems that inherit this idea¶

Codeforces — Devu and his Brother (https://codeforces.com/problemset/problem/439/D) — cost function unimodal-ঘরানা; ternary search/বুদ্ধি প্রয়োগ।
LeetCode — Peak Index in a Mountain Array (https://leetcode.com/problems/peak-index-in-a-mountain-array/) — unimodal array-এর চূড়া; ternary/binary search-এর সরাসরি প্রয়োগ।
CP-Algorithms — Ternary Search (https://cp-algorithms.com/num_methods/ternary_search.html) — তত্ত্ব ও আরও প্রয়োগ।

19. Pattern learned¶

Ternary search on unimodal functions — একটাই চূড়া/খাদ থাকলে দুটো probe (m1, m2) দিয়ে এক-তৃতীয়াংশ ফেলে দাও; range ⅔ করে কমে, O(log(1/ε))-এ চূড়া। শর্ত: unimodality (আগে যাচাই করো)।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "একটাই চূড়া/খাদ (unimodal) দেখলে ternary search — দুই probe m1, m2, f(m1)<f(m2) হলে lo=m1 নাহলে hi=m2, range ⅔ করে কমাও। আগে unimodality নিশ্চিত করো, নাহলে চুপচাপ ভুল হবে।"

পরের ধাপ → 141 — Game Theory Basics (game theory trilogy শুরু — পেছন থেকে W/L label)। শিকড় → 091 — Binary Search ঘরানা।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।