from typing import Dict


def get_avg_accuracy(validation_accuracy: Dict[float, float], budget: float) -> float:
    """
    Gets the average validation accuracy for the two budgets closest to the given budget.
    If the budget is out of the range of the dictionary, we return the accuracy
    of the nearest budget.
    """
    budget_under, budget_over = None, None
    for b in validation_accuracy.keys():
        if b < budget and (budget_under is None or b > budget_under):
            budget_under = b

        if b > budget and (budget_over is None or b < budget_over):
            budget_over = b

    if budget_under is None:
        assert budget_over is not None, 'Could to find bounds for {0}'.format(budget)
        return validation_accuracy[budget_over]
    elif budget_over is None:
        assert budget_under is not None, 'Could to find bounds for {0}'.format(budget)
        return validation_accuracy[budget_under]
    else:
        return (validation_accuracy[budget_under] + validation_accuracy[budget_over]) / 2