หาตำแหน่งในลำดับมโนโทนิก f(m) = am + bm[log2(m)] + cm³ (Python)

โจทย์: กำหนด a,b,c และค่าเป้าหมาย l หา m ที่ f(m) = l โดย f(m) = a·m + b·m·⌊log₂(m)⌋ + c·m³ หาไม่เจอ → 0

ตัวอย่าง: a=2,b=1,c=1,l=12168587437017 → m=23001

อัลกอริทึม Binary Search

f(m) เพิ่มขึ้นอย่างเคร่งครัด (monotonic increasing) เพราะ a,b > 0, c ≥ 0 → ใช้ Binary Search หา m

1. คำนวณ f(m) = a·m + b·m·⌊log₂(m)⌋ + c·m³
2. ช่วงค้นหา: c=0 → high=10¹⁵ (ใหญ่), c>0 → high=10⁶ (เพราะ m³ เติบโตเร็ว)
3. Binary search ปกติ หา m ที่ f(m) = l

ตัวอย่างโค้ด

from math import log2, floor

SMALLER_VAL = 1_000_000
LARGER_VAL = 1_000_000_000_000_000

def solve(a, b, c, n):
    ans = a * n
    lg_val = floor(log2(n))
    ans += b * n * lg_val
    ans += c * n**3
    return ans

def get_pos(a, b, c, k):
    begin, end = 1, SMALLER_VAL
    if c == 0:
        end = LARGER_VAL
    ans = 0
    while begin <= end:
        mid = (begin + end) // 2
        val = solve(a, b, c, mid)
        if val == k:
            ans = mid
            break
        elif val > k:
            end = mid - 1
        else:
            begin = mid + 1
    return ans

print(get_pos(2, 1, 1, 12168587437017))  # 23001

ผลลัพธ์

23001

สรุป: Binary Search บนฟังก์ชันมโนโทนิก O(log MAX) time การตั้ง high bound ขึ้นอยู่กับ c: c=0 ต้องใหญ่ (linear/log), c>0 ใช้ m³ จำกัดได้ที่ ~10⁶