Finding the right amount to save away


I am currently learning python and as a little test a friend of mine gave me a problem from the MIT open courseware python course. However, I am struggling on part C of the problem. It requires that you use a binary search to find the right amount you need to save if you want to buy a house in 3 years given a starting salary.

Here is the problem pdf for further details (scroll to part C):

I have technically "solved" it and am able to find the correct value according to the test cases given but the percents have many digits and the amount of bisection searches counted is much higher than that of the test cases.

I was wondering if there is actually anything wrong with my code and if I am implementing the binary search correctly with regards to this problem.

Example test cases:
Test Case 1:

Enter the starting salary:​ 150000

Best savings rate:​ 0.4411

Steps in bisection search:​ 12


Enter the starting salary:​ 150000

Best savings rate:​ 0.4411391177390328

Steps in bisection search:​ 40

Thanks for any help!

Apologies in advance for this question I am still learning ;P

My Code:

annual_salary = float(input('Enter the starting salary: '))
constant = annual_salary
semi_annual_rate = 0.07
r = 0.04
down_payment = 0.25
total_cost = 1000000
current_savings = 0
months = 0
bisection_count = 0
min = 0 
max = 1
portion_saved = (max/2.0)/1000
    print('It is not possible to pay the down payment in three years.')

        current_savings += (current_savings*r/12)+(portion_saved*(annual_salary/12))
        if(months % 6 == 0):
            annual_salary += annual_salary*semi_annual_rate
    if(current_savings >= down_payment*total_cost+100):
        max = portion_saved
        portion_saved = max/2.0
        months = 0
        current_savings = 0
        annual_salary = constant
    elif(current_savings >= down_payment*total_cost-100 and current_savings <= down_payment*total_cost+100):
        min = portion_saved
        portion_saved = (max+min)/2.0
        months = 0
        current_savings = 0
        annual_salary = constant

print('Best savings rate: ', portion_saved)
print('Steps in bisection search: ', bisection_count)


The line which causes too many iterations is

portion_saved = max/2.0

You should simply do

portion_saved = (max+min)/2.0

as you correctly do some lines below.

Note you’re not strictly respecting the assignment since it asks to use int values in the range 0-10000 for portion_saved, not float – in this test case it even comes as a slight advantage because you get 11 iterations instead of 12, but in other cases it may be the other way round. Anyhow if you want to keep using float you may just format the result.

One last, very important thing: please don’t use min and max as variable names. You’re overwriting two built-in functions, so should you ever need to do min(5,2,7) you would get

TypeError: 'float' object is not callable
Leave a Reply

Your email address will not be published. Required fields are marked *