Performing a Binary Search

Question

I am performing a binary search , let say i have to find the minimum value of x such that black_box(x) gives me true result.

Property of black_box(x)

If black_box(x) gives me true then x+1,x+2,x+3,x+4....upto infinty all gives me true

For Integer Value this is simple binary search

 start=0;
 end = Max;
 ans=-1;
 while(start<=end){

    mid =(start+end)/2;
   if(black_box(mid)):
       end =mid-1
       ans=mid;
   else: start=mid+1;
}

What if i want a floating point integer upto 2 decimal , how should i do binary search ?

If end = Inf, how can you determine the middle of it? Even for ints that's not the case. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jan 6, 2017 at 10:20
@WillemVanOnsem It's smiple expression , Inf will the maximum value , just a representation , hope you get this — Narendra Modi
– Narendra Modi, Commented Jan 6, 2017 at 10:22
yeah but there are ways to represent integers with no maximum value (or at least not until you run out of memory, like BigInteger in Java. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jan 6, 2017 at 10:23

willeM_ Van Onsem · Accepted Answer · 2017-01-06 10:26:26Z

1

You simply iterate until start and end differ no more than 0.01. So the stop condition is now:

while(end-start > 0.01){

Furthermore as you specified in the comment yourself, you cannot increment/decrement start and end in your algorithm, since the indices are not discrete. The full algorithm now is:

 start=0;
 end = Max;
 ans=-1;
 while(end-start > 0.01){

    mid =(start+end)/2.0;
   if(black_box(mid)):
       end =mid
       ans=mid;
   else: start=mid;
}

This works because at each iteration start is a lower bound on the exact value and end is an upper bound on the exact value. If both no differ more than 0.01, we know it is in the range between start and end and since the difference is less than 0.01, it is exact by two decimals.

Nevertheless, your algorithm is wrong in the sense that by setting end = Inf, you cannot work with this. You can perhaps use the maximum representable value, or use exponential increment search first as a preprocessing step.

edited Jan 6, 2017 at 10:26

answered Jan 6, 2017 at 10:21

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Narendra Modi Over a year ago

What about the increment i am increment with +1

willeM_ Van Onsem Over a year ago

@NarendraModi: simply set end = mid and start = mid, so without increments/decrements.

Collectives™ on Stack Overflow

Performing a Binary Search

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related