## J.Soto one year ago Can someone take a look at my code and tell me why this isn't working. I'm trying to do problem 3 in problem set 3. I'm having trouble implementing bisection search into the original code I wrote for problem 2. I'll attach the code in a file, any help would be appreciated.

1. J.Soto

The code is here.

2. e.mccormick

In a typical bisection search you are saying, "Let me guess, and to make it easy, let me guess half way in the middle. Is my guess higher or lower than the acceptable answer?" If lower, you take half way from the guess to the top, make the old guess the new low point, and test again. If higher you take half way from the test to the bottom, make the old guess the high point, and test again. Does that make sense?

3. J.Soto

Hmmm, I think understand what your trying to say. Ok, I'll try and work it out. Thank you for your input.

4. e.mccormick

So the search result for say the number 17 out of 1 to 100 would be basically this: high = 100 low = 1 guess (half way between high and low) = $$\quad$$(high-low)/2 + low = (100 - 1)/2 + 1 Is guess correct, higher, or lower? Higher set high to 50 guess = (50-1)/2 + 1 = 25 Is guess correct, higher, or lower? Higher set high to 25 guess = (25-1)/2 + 1 = 13 Is guess correct, higher, or lower? Lower set low to 13 guess = (25-13)/2 + 13 = 19 Is guess correct, higher, or lower? Higher set high to 19 guess = (19-13)/2 + 13 = 16 Is guess correct, higher, or lower? Lower set low to 16 guess = (19-16)/2 + 16 = 17 Is guess correct, higher, or lower? Correct Now, I am discarding decimals, so there will be difference because the question uses floating point math. So "correct" is actually a range, or epsilon.

5. J.Soto

The issue that I'm having is that somewhere in my code there is an error that I can't seem to find. I have a nested while loop that runs 12 times with the current value of minmonp (my minimum payment) and if at any point the ob (outstanding balance) is equal to or less than 0 the loop and it's parent loop break. If however the minmonp is not enough to get ob below or equal to 0 in 12 months the nested while loop breaks and the parent loop sets the current minmonp as the new low and then re-initiates minmonp with the new low. It logically seems correct to me since if it was high enough to pay the bill then the program would end and if it wasn't, it would keep running and yet I keep getting returns that are too low. I'm just a bit confused, I understand how to use bisection in theory but I am messing up with the implementation of it in my particular case. I haven't yet accounted for a minmonp that is greater than the answer, but I will after I figure out why I keep getting answers that are too low. I would think that they would be higher since I am explicitly ignoring answers that are too low. Thanks in advance for your help.

6. J.Soto

I now see the issue I wasn't paying attention to my program output it's actually to high so I just have to set that as the new high and find an epsilon that's close enough for me. Thanks for you help again mccormick.

7. e.mccormick

Ah, there. Now you seem to have gotten the point of my two comments. How bisection jumps between high and low and that the key is being close enough (within epsilon) of the answer. I did a version of this where you put in the target number of months and balance. What it did was divide the balance by months + 1 for the first attempt to pay it off in that many months. Then, whatever it was short by, it divided that by months + 1 and added it to the monthly payment. So each step it gets a little closer to being there. One safeguard to put in is the amount added must be more than 1, otherwise just add 1. That way it does not fall into one of Zeno's Paradoxes: if you only go half the way every time, you never get there because there is always half the remaining distance. That is another way of cutting down the number of increments, but only works if you know you can come up to something slowly. The radix sort is another example of how to sort and find things quickly. In radix, you use buckets to collect similar things, then work within each bucket. So for 3 digit numbers there is the 000 to 099 bucket, the 100 to 199 bucket, and so on. Inside each bucket you make smaller buckets, and keep working with less and less until everything is sorted or you have found what you need.