May 7th, 2018, 12:44 PM  #1 
Newbie Joined: Jan 2016 From: england Posts: 17 Thanks: 0  Binary Search
If f(x)=0 and a<x<b Computing the following gives: f(a)<0 f(b)>0 f((a+b)/2)>0 By using a binary search, how many iterations would be needed to arrive at an answer correct to 4dp? I'm completely lost here, am I looking in the right place with Binary logarithms? I have found the following: log_2x=n+log_2y where y=2^(n) x and y∈[1,2) But I'm not sure if I'm barking up the wrong tree here. Please help...! 
May 7th, 2018, 12:51 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,274 Thanks: 1959  
May 7th, 2018, 02:04 PM  #3 
Newbie Joined: Jan 2016 From: england Posts: 17 Thanks: 0 
Sorry, the solution to f(x)=0. I am trying to determine the amount of calculations it would take, in terms of a and b, to find an answer that would be correct to 4dp. By calculations I mean, 1st calculation is f(a), 2nd is f(b) and 3rd is f((a+b)/2). These then repeat in the binary search 
May 7th, 2018, 02:31 PM  #4 
Global Moderator Joined: May 2007 Posts: 6,683 Thanks: 658 
There is no obvious solution, because the shape of the function may preclude it. A function which is almost flat {negative} from a to a point near be and then starts rising rapidly to be positive at be would have a zero near b which would take many steps to find.

May 7th, 2018, 08:50 PM  #5 
Senior Member Joined: Sep 2016 From: USA Posts: 556 Thanks: 321 Math Focus: Dynamical systems, analytic function theory, numerics 
This question is meaningless. Find an answer to what? Is $f$ continuous? monotone? Lipschitz? I suspect you are leaving out a great deal of information. Assuming you are looking to converge to a zero of $f$? How would you use binary search for the function \[ f(x) = \left\{ \begin{array}{cc} 1 & x \in \mathbb{Q} \\ 0 & x \notin \mathbb{Q} \end{array} \right.\] with $a,b$ irrational (and algebraically independent)? What about the function $f(x) = \frac{1}{x}$? 
May 8th, 2018, 12:32 AM  #6 
Senior Member Joined: Aug 2012 Posts: 2,156 Thanks: 630 
I think binary search just means that we take the midpoint of the interval and ask if the zero is in the left or right subinterval defined by that midpoint. Then we take the left or right subinterval and test with its midpoint. In this way we are guaranteed to be within $\frac{1}{2^n}$ of the zero after $n$ iterations. That's if we start with the interval $(a,b) = (0,1)$ for simplicity. In this case we are given that $f(\frac{a+b}{2}) > 0$. So we can skip the first iteration since we are told that the zero must be in the left half of the starting interval. Perhaps they mean for us to take this into account. Now four decimal places is $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ so normally we'd need 10 iterations to guarantee that our trial value is within four decimal places of the actual zero. But we got the first iteration for free, so the answer is 9. That last bit's a bit speculative but why else would they tell us the value at the initial midpoint? That's how I would interpret this problem. It's entirely independent of the nature of $f$, which could be arbitrarily wild and it would make no difference. The assumption is that there is an oracle that, given n, returns "left," "right," or "bingo" when you input the nth subinterval. Once you have that it's just a matter of seeing how finely you need to chop up the original interval with negative integer power of 2 sized subintervals to get as close as you want to the actual zero. Of course, this answer of 9 (or 10, depending how you interpret it) iterations is the max. In special cases it could be less. For example, if $f$ is the characteristic function of the rationals, you can pick any value of $x$ at all and be certain you're within four decimal places of some zero of the function. Last edited by skipjack; May 8th, 2018 at 10:02 AM. 
May 8th, 2018, 12:47 AM  #7 
Newbie Joined: Jan 2016 From: england Posts: 17 Thanks: 0 
Thanks so much Maschke, this is exactly what I was looking for, you've explained it perfectly. Thank you!!

May 8th, 2018, 12:51 AM  #8  
Senior Member Joined: Oct 2009 Posts: 733 Thanks: 246  Quote:
Last edited by skipjack; May 8th, 2018 at 10:03 AM.  
May 8th, 2018, 09:48 AM  #9  
Senior Member Joined: Aug 2012 Posts: 2,156 Thanks: 630  Quote:
I agree with you that the condition that f(a) and f(b) are on opposite sides of the real line is a clue that OP was being asked about continuous functions, but we don't actually need that assumption for this problem. Last edited by Maschke; May 8th, 2018 at 09:56 AM.  
May 9th, 2018, 07:36 PM  #10 
Senior Member Joined: Aug 2012 Posts: 2,156 Thanks: 630 
p.s.: $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ is wrong of course. The righthand side of the inequality should be $\frac{1}{2^{14}}$.
Last edited by skipjack; May 9th, 2018 at 07:57 PM. 

Tags 
binary, search 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Binary search tree problem  motant  Computer Science  0  April 19th, 2015 01:43 PM 
Average search cost of an unsuccessful search in a BST?  flexdec  Applied Math  0  July 16th, 2013 06:25 AM 
specific search  andreaugust  Number Theory  2  July 15th, 2013 06:30 AM 
Extremum search  thescratchy  Calculus  6  March 5th, 2011 07:41 PM 