Python. Найти число, удовлетворяющее условию

Question

На вход подается список h, элементы в нем расположены по возрастанию. Необходимо найти такое число k, при котором функция f() будет возвращать минимальное значение. Код функции f():

def f(l):
    s = 0    
    for i in range(len(h)):
        if (h[i] - l > 0):
            s += (1 + h[i] - l)/2*(h[i] - l)
        else:
            s += (1 + l - h[i])/2*(l - h[i])           

    return s

Пример: Если h = [2, 3, 5, 29], то k = 9

Подскажите пожалуйста, как найти такое k? Я пытался сделать бинарный поиск, но не получилось

min_s = 10**1000

h = [2, 3, 5, 29]

l = h[0]
r = h[len(h)-1]
while l != r - 1:
    m = (l + r) // 2
    e = f(m)
    if e >= min_s:
        l = m
    else:
        r = m
        min_s = e
print(l, min_s)

Answer 1

Можно сделать в лоб:

def f(l, h):
    s = 0    
    for i in range(len(h)):
        if (h[i] - l > 0):
            s += (1 + h[i] - l)/2*(h[i] - l)
        else:
            s += (1 + l - h[i])/2*(l - h[i])           

    return s


h = [2, 3, 5, 29]

k_min = -100
f_min = f(k_min, h)

for k in range(-100, 100):
    f_current = f(k, h)

    if f_current < f_min:
        f_min = f_current
        k_min = k

print(k_min, f_min)

кстати функцию f можно упростить:

def f(l, h):
    s = 0
    for i in range(len(h)):
        r = h[i] - l
        if (h[i] - l > 0):
            s += (r + r * r)
        else:
            s += (-r + r * r)

    return s / 2

Answer 2

Я бы сделал вообще ход конем:

функция f может быть представлена в виде

def f(l, h):
    s = 0
    for i in range(len(h)):
        r = h[i] - l
        if (h[i] - l > 0):
            s += (r + r * r)
        else:
            s += (-r + r * r)

    return s / 2

или так (на математическом языке):

s = sum[(k - h_i)**2 +- (k - h_i)] / 2

плюс-минус в зависимости от выполнения условия (k - h_i) > 0

Найдем минимальное значение с помощью математического анализа - т.е. надо найти производную, приравнять нулю и найти k

s' = 2 * k - 2 * h_i -+ 1 = 0

поскольку этот плюс-минус мы можем определить только перебрав элементы списка, то аналитически можно решить задачу, найдя минимальный и максимальный k

s' = sum[2 * k_min - 2 * h_i + 1] = 0
s' = sum[2 * k_max - 2 * h_i - 1] = 0

откуда

k_min = sum[h_i] / len(h) - 0.5
k_max = sum[h_i] / len(h) + 0.5

в итоге надо перебрать всего 3 значения для k и не важно был отсортирован список h или нет

а поскольку k у нас должны быть целыми, то имеем ответ

k = round(sum[h_i] / len(h))

но я все таки проверил бы боковые k тоже

БЛОГ НА HUSL

Python. Найти число, удовлетворяющее условию

Ответы (2 шт):