interpolated_factor.py

"""
x Coverages = [100000, 150000, 200000, 250000, 300000, 350000]
y Factors = [0.971, 1.104, 1.314, 1.471, 1.579, 1.761]

Write a function that takes x2 (coverage selected by customer), a list of coverages (x) and a list of factors (y) and returns y2 (interpolated factor)
Performance is important.  Build a solution for a list with 1000 elements.  The Coverages list will always be sorted.
linear interpolation formula:

y2 = (x2 - x1) (y3 - y1) / (x3 - x1) + y1

solve = (selected - x) (y2 - y) / (x2 - x) + y

"""


def check_bounds(selected, coverages):
    lowest = coverages[0]
    highest = coverages[-1]
    if selected < lowest or selected > highest:
        raise AttributeError(f"{selected} OUT OF RANGE({lowest} -> {highest})")


# O(log n)
def binary_searchish(selected, coverages):
    check_bounds(selected, coverages)

    low = 0
    high = len(coverages) - 1

    while low <= high:
        mid = (high + low) // 2

        if coverages[mid] < selected:
            low = mid + 1

        elif coverages[mid] > selected:
            high = mid - 1

        else:
            break

    return mid


def solve(selected, coverages, factors):

    upper = binary_searchish(selected, coverages)
    lower = upper - 1

    x1, y1 = coverages[lower], factors[lower]

    if selected == x1:
        return y1

    x3, y3 = coverages[upper], factors[upper]

    if selected == x3:
        return y3

    return (selected - x1) * (y3 - y1) / (x3 - x1) + y1


COVERAGES = [100000, 150000, 200000, 250000, 300000, 350000]  # X
FACTORS = [0.971, 1.104, 1.314, 1.471, 1.579, 1.761]  # Y

SELECTED = 300400

result = solve(SELECTED, COVERAGES, FACTORS)

print(result)