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