Python Bisect Search- abs() causing failure
<p>So I am attempting to implement a <strong>bisection search algorithm</strong> in Python that returns an "optimal" savings rate.</p>

<p>I've tried creating several different functions, and I don't understand why the program gets caught in an infinite loop. I do know that the abs(current_savings - down_payment) is what causes the recursive infinite loop but I do not know why.</p>

<p>First things first, this doesn't really explain why my program doesn't work but here goes:</p>

<blockquote>
  <p>At the end of each month I earn interest on current savings, which is
  applied first, and then I receive my monthly salary, which is just
  1/12 of my annual salary.</p>
</blockquote>

<p>I am attempting to find the best rate to apply to my monthly salary, to then add to my current savings. </p>

<p>My first function simply checks to see if one's salary is high enough to ever save for the 250K down payment. If their salary is not high enough, it prints that it is not adequate and returns False. </p>

<p>My second function attempts to find the best rate ("portion saved"), or the best rate to save of monthly salary in order to fall within 100 dollars of the down_payment. In addition, I must record the number of "steps" my bisection search function takes to find the optimal rate. </p>

<p>Here is the code:</p>

<pre><code>    #Givens
annual_salary = 150000
initial_salary = annual_salary
interest_rate = float(0.04/12.0)
down_payment = float(250000.0)
semi_annual_raise = 0.07

#Bisect-search
low = float(0.0)
high = float(10000.0)
portion_saved = float((low+high)/2)
current_savings = 0
months = 0
steps = 0

def isPossible(annual_salary):
    count = 0
    current_savings = 0
    while count &lt; 36:
        current_savings += (current_savings*interest_rate) + (annual_salary/12)
        count += 1
        if count % 6 == 0:
            annual_salary += (annual_salary*semi_annual_raise)
    if current_savings &lt; down_payment:
        print("ItÂ isÂ notÂ possibleÂ toÂ payÂ theÂ downÂ paymentÂ inÂ threeÂ years.")
        return False
    else:
        return True


def bisearch(initial_salary,interest_rate,down_payment,semi_annual_raise,low,high,portion_saved,steps):
    current_savings = 0
    months = 0
    while abs(current_savings - down_payment) &gt; 100.0:
        months = 0
        current_savings = 0
        while months &lt; 36:
            current_savings = current_savings + (initial_salary*interest_rate)
            current_savings = current_savings + (initial_salary/12*portion_saved/10000.0)
            months += 1
            if months % 6 == 0:
                initial_salary += (initial_salary*semi_annual_raise)
        steps += 1
        if current_savings &gt; down_payment:
            high = portion_saved
        else:
            low = portion_saved
        portion_saved = ((low+high)/2.0)
    print("Best saving rate: ", (portion_saved/10000.0))
    print("Steps in bisection search: ", steps)




if isPossible(annual_salary) == True:
    bisearch(initial_salary,interest_rate,down_payment,semi_annual_raise,low,high,portion_saved,steps)
</code></pre>

<p>And the test cases:</p>

<p><strong>Note:</strong> the number of bisection search steps doesn't have to be the same, but the rate should be the same</p>

<p>TestÂ CaseÂ 1</p>

<pre><code>EnterÂ theÂ startingÂ salary:Â 150000

BestÂ savingsÂ rate:Â 0.4411

StepsÂ inÂ bisectionÂ search:Â 12
</code></pre>

<p>TestÂ CaseÂ 2</p>

<pre><code>EnterÂ theÂ startingÂ salary:Â 300000

BestÂ savingsÂ rate:Â 0.2206

StepsÂ inÂ bisectionÂ search:Â 9
</code></pre>

<p>If anyone could help me out I would greatly appreciate it, been at this for hours trying to come up with a fix. </p>

<p>I was confused in the same problem and finally found a solution. Try resetting initial_salary back to annual_salary inside the first while loop within your bisection function, else that would just keep on increasing every time you hit six months on the inner loop. Does that work?</p>

python python-3.x bisection