My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Thanks Tree1Thanks
  • 1 Post By Maschke
Reply
 
LinkBack Thread Tools Display Modes
May 7th, 2018, 11:44 AM   #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_2⁡x=n+log_2⁡y 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...!
Skykai is offline  
 
May 7th, 2018, 11:51 AM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 19,515
Thanks: 1745

Quote:
Originally Posted by Skykai View Post
. . . would be needed to arrive at an answer correct to 4dp?
An answer to what?
skipjack is online now  
May 7th, 2018, 01: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
Skykai is offline  
May 7th, 2018, 01:31 PM   #4
Global Moderator
 
Joined: May 2007

Posts: 6,582
Thanks: 610

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.
mathman is offline  
May 7th, 2018, 07:50 PM   #5
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 438
Thanks: 249

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}$?
SDK is online now  
May 7th, 2018, 11:32 PM   #6
Senior Member
 
Joined: Aug 2012

Posts: 1,999
Thanks: 573

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 n-th 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.
Thanks from Skykai

Last edited by skipjack; May 8th, 2018 at 09:02 AM.
Maschke is offline  
May 7th, 2018, 11:47 PM   #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!!
Skykai is offline  
May 7th, 2018, 11:51 PM   #8
Senior Member
 
Joined: Oct 2009

Posts: 456
Thanks: 148

Quote:
Originally Posted by Maschke View Post
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 n-th 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.
It's still crucial the function is continuous though, to even guarantee the existence of a root to begin with.

Last edited by skipjack; May 8th, 2018 at 09:03 AM.
Micrm@ss is offline  
May 8th, 2018, 08:48 AM   #9
Senior Member
 
Joined: Aug 2012

Posts: 1,999
Thanks: 573

Quote:
Originally Posted by Micrm@ss View Post
It's still crucial the function is continuous though, to even guarantee the existence of a root to begin with.
As I understand this problem, it's only necessary that the function has at least one root; and that there's an oracle that responds "left" or "right" or "bingo" correctly. The OP said there's at least one root.

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 08:56 AM.
Maschke is offline  
May 9th, 2018, 06:36 PM   #10
Senior Member
 
Joined: Aug 2012

Posts: 1,999
Thanks: 573

p.s.: $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ is wrong of course. The right-hand side of the inequality should be $\frac{1}{2^{14}}$.

Last edited by skipjack; May 9th, 2018 at 06:57 PM.
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 12:43 PM
Average search cost of an unsuccessful search in a BST? flexdec Applied Math 0 July 16th, 2013 05:25 AM
specific search andreaugust Number Theory 2 July 15th, 2013 05:30 AM
Extremum search thescratchy Calculus 6 March 5th, 2011 06:41 PM





Copyright © 2018 My Math Forum. All rights reserved.