Binary search works for integer arrays, but not for double arrays

Question

I am working through one of the examples in the Intro to Java textbook 10th edition by Daniel Liang. I ran into an issue in Chapter 7 when performing a binary search on a single dimensional array. My code works fine when I use it on an integer array, but it does not work when I input a double.

update: 4/25/2020 1:20pm Eastern Time USA

I updated the code to reflect the double array and double key in method signature. I have also include a method call. I tried the approximation solution by introducing

static boolean equals(double a, double b){
        if (Math.abs(a - b) <= epsilon) return true;
        return false;

and then calling it in the binary search method as follows:

while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (equals(key, a[mid]))
                return mid;
            else
                low= mid + 1;

I am unsure if the issue is losing precision because even though I am using doubles, they are all whole numbers. Below is the original code from the textbook- method signature changed to reflect double.

class Scratch {

//I created two class array variables here to test the binary search approach. 

static double[] myList = {12.0,34.0,5.0,6.0,78.0,89.0,0.0};
static int[] a = {5,1,3,3,4};

//Main method call 
public static void main(String[] args) {
      System.out.println(binarySearch(myList, 12.0));


    }
public static int binarySearch(double[] a, double key){
        int low = 0;
        int high = a.length-1;
        while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (key == a[mid])
                return mid;
            else
                low= mid + 1;
        }
        return -low -1;
    }

The computer is printing a negative number signaling that the key was not found.

Thank you!

Answer 1

Like others have mentioned, the double type has a precision limit.

What you might consider doing is change this line else if (key == a[mid]).

And instead of making a strict ==, you can try to introduce a "good enough" criteria. for example

// it can really be any number. depending on how "precise" you want
static double epsilon = 1e-9; 
static boolean equals(double a, double b) {
    if (Math.abs(a-b) <= epsilon) return true; 
    return false; 
}
... 
...
else if (equals(key, a[mid])) return mid; 
...

EDIT: In order for the binary search algorithm to work, the array must be SORTED. The key idea behind binary search Divid and Conquer.

The idea behind it is quite straight forward: For a big problem, if we can reduce the complexity of solving it, then it becomes a smaller problem. (step 1) If somehow we can reduce the smaller problem into an even smaller problem (possibly by re-applying the technique in step 1), it is even one step closer to finding the solution (step 2). In each step, we keep getting closer and closer until the problem becomes so trivial to solve.

I recommend watching some good videos online, for example, this one

Answer 2

You have not given us enough information to know for sure how you got a glitch, but I am going to guess that you did something like this:

double[] a = ...     // create and initialize
int i = ...          // a valid subscript for 
int result = binarySearch(a, (int)(a[i])); 
                     // result is -1

Here's why that doesn't work.

• When you cast a floating point value to an integral type, you may loose precision; i.e. 1.5 becomes 1 and you have lost the 0.5.
• When you compare a floating point type and an integral type using ==, <, > and so on, the integral value is converted to the nearest value in the floating point type ... before the numbers are compared. This conversion could also loose precision.

So, when we look what your code is doing, you will be taking an double in your a array, casting it to an int so that you can use it as the key ... then converting key back into a double each time that binarySearch does a comparison.

double -> int -> double.

The reason you are seeing glitches is that initial double and the final double are not the same for the a[i] that you are searching for. So == is giving you false when you want it to be true.

The solution is to change the type of key to be the same as the base type of the array that you are searching. So that there is no need to cast or convert values.

---

Ulilop raises another relevant point in his answer. Even if we exclude the conversions I described above, computer floating point and floating point arithmetically are fundamentally imprecise. So for example:

double one_third = 1.0 / 3.0;
double one = one_third * 3.0;
System.printf(one == 1.0);       // prints "false" !!!!

So whenever you do anything involving the comparison of floating point values you need to take account of the possibility of rounding errors in the computation.

For more on this topic, read these:

• Why are floating point numbers inaccurate?
• Is floating point math broken?

---

FINALLY you have provided us with your real code.

The reason your real code is giving you the wrong answer is that you are performing a binary search in an array that is not ordered. Binary search only works if the array you are searching is ordered. As Wikipedia states:

"In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array."

Answer 3

Does the double it's an exact number?

When you compare doubles and integers, a variation in the decimal value will make the comparison statement false.

A workaround can be casting the double to int when comparing.

public class Main {
    public static void main(String[] args) throws Exception {
        double d1 = 100.000000001;
        double d2 = 100.000000000;
        int i = 100;

        System.out.println(d1 == i);
        System.out.println(d2 == i);
        int int1 = (int)d1;
        int int2 = (int)d2;

        System.out.println(int1 == i);
        System.out.println(int2 == i);
    }
}

The output:

false
true
true
true