Determining a salary for buying a house in 36 months
I don't think your code is an inefficient bisection search.  The example which needed fewer iterations could simply be getting lucky and getting within the $100 terminal condition on one of its earlier steps.  That said, here are a couple of implementation pointers:
Don't recalulate salary
The salary used in the loop, increases every six months.  But it does not change based on savings rate, so is the same for every guess.  Therefore calculate it once before starting the guessing.  It could look something like this:
monthly_salary = [annual_salary / 12]
for month in range(2, 37):
    monthly_salary.append(monthly_salary[-1])
    if month % 6 == 1:
        monthly_salary[-1] *= (1 + semi_annual_raise)
        

Or using itertools, something like this:
import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))          
    

Consider using itertools.accumulate()
The loop which sums up the savings can be done using itertools.accumulate().  Basically you define a function which is passed the previous total and an element from an iterable.  Then returns the next total.
def accum(total, salary):
    return total * (1 + r / 12) + salary * portion_saved

Then the function, and an iterable is passed to accumulate:
*_, current_savings = it.accumulate(monthly_salaries, accum)

Finally the *_, current_savings = ... can be used to gather the last item in an iterable.
The *_ is rather cryptic.  The _ is just a variable name that is often used in Python to indicate that it is unneeded.  The * is used for variable expansion.  See Pep 448 for more details.
Revamped code:
annual_salary = 150000
total_cost = 1000000
semi_annual_raise = .07
portion_down_payment = total_cost * 0.25
current_savings = 0
r = 0.04
guesses = 0
low = 0
high = 1

import itertools as it
import operator
salaries = [annual_salary / 12] + [1 + semi_annual_raise] * 5
monthly_salaries = [0] + list(it.chain.from_iterable(
    (x,) * 6 for x in it.accumulate(salaries, operator.mul)))

portion_saved = (low + high) / 2
while abs(portion_down_payment - current_savings) &gt; 100:

    def accum(total, salary):
        return total * (1 + r / 12) + salary * portion_saved

    *_, current_savings = it.accumulate(monthly_salaries, accum)

    if current_savings &gt;= portion_down_payment:
        high = portion_saved
    else:
        low = portion_saved

    portion_saved = (low + high) / 2
    guesses += 1

print(portion_saved, guesses)