Binary search not working - NON array.

Question

I'm not sure if this is an issue with my formula or my thought process. This is an exercise from CodeAbbey so not looking for the specific answer, just a push in the right direction.

I understand binary searches when it comes to array's. Here we're trying to use it to solve an equation. This is the example:

A * x + B * sqrt(x ^ 3) - C * exp(-x / 50) - D = 0

This is my formula where mid serves as x:

double result = (((a * mid) + (b * (Math.sqrt(Math.pow(mid, 3.0)))) - (c * (Math.exp(-mid / 50)) - d)));

This is a test case they give:

Data:

1
0.59912051 0.64030348 263.33721367 387.92069617

Result should be:

73.595368554162

I think it's my formula. If I plug in that result I do not get 0 as I assume I should.

Which is why I never get exited from my while loop.

package com.secryption.CA34BinarySearch;

import java.util.Scanner;

/**
 * Created by bmarkey on 11/11/2015.
 */

public class BinarySearch {
    public static void main(String[] args) {
        Scanner scanner1 = new Scanner(System.in);
        System.out.println("Enter Data: ");
        int testCases = scanner1.nextInt();

        for (int i = 0; i < testCases; i++) {
            double a = scanner1.nextDouble();
            double b = scanner1.nextDouble();
            double c = scanner1.nextDouble();
            double d = scanner1.nextDouble();
            boolean solved = false;

            double upperBound = (c + d) / (a + b);
            double lowerBound = 0;
            double mid;

            while (!(solved)) {

                mid = (upperBound + lowerBound) / 2.0;
                double result = ((a * mid) + (b * (Math.sqrt(Math.pow(mid, 3.0)))) - (c * (Math.exp(-mid / 50)) - d));

                if (result > 0) {
                    upperBound = mid;
                } else if (result < 0) {
                    lowerBound = mid;
                } else {
                    System.out.println(mid);
                    solved = true;
                }
            }
        }
    }
}

Alnitak · Accepted Answer · 2015-11-12 16:27:53Z

4

Get rid of the extra parentheses, and you'll see that your - d term has become incorrectly multiplied by the c term.

You'll probably also need to compare to something very close to zero, since in testing this I found that the result variable doesn't exactly reach zero because of floating point inaccuracies, i.e:

if (Math.abs(result) < 1e-10) {
      System.out.println(mid);
      solved = true;
} else if (result > 0) {
      upperBound = mid;
} else if (result < 0) {
      lowerBound = mid;
}

edited Nov 12, 2015 at 16:27

answered Nov 12, 2015 at 15:26

Alnitak

341k72 gold badges420 silver badges503 bronze badges

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

7 Comments

TheEditor Over a year ago

that worked thanks. Why was that happening? I assumed that (Math.exp(-mid / 50)) would calculate, then be multipled by c then d subtracted from that.

Alnitak Over a year ago

@TheEditor you had the - d too far inside the parentheses, i.e. you had (c * (... - d)) instead of (c * (...) - d)

TheEditor Over a year ago

Ok. Got it. I knew it was going to be something simple like that. Lesson learned.

Alnitak Over a year ago

You actually had far too many parens all around - in general for maths expressions the normal rules apply, so you could have just got away with: result = a * mid + b * Math.pow(mid, 1.5) - c * Math.exp(-mid / 50) - d (taking advantage of sqrt(x^3) == x^1.5)

TheEditor Over a year ago

Good information. I am trying to break that habit of too many parens. I'm working on it.

|

Collectives™ on Stack Overflow

Binary search not working - NON array.

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related