I am trying to create a program that does a binary search of array of randomly generated doubles and when I try to run the code, I get this error.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 9999 out of bounds for length 9999
    at Search.binarySearch(Search.java:34)
    at Search.main(Search.java:17)

I tried changing the array size and making it smaller and bigger, but I always get a error. I don't know what less I can do. Here is the code.

import java.lang.Math;
import java.util.Arrays;
import java.util.Random;

class Search{
    public static void main(String [] args){
        double [] array2  = new double [9999];  
        for(int i = 0; i <array2.length;i  ){   
            array[i] = (double) (Math.random() * 9999); 
        }
        Arrays.sort(array);
        System.out.println(binarySearch(array, new Random().nextDouble(9999)));
    }

    public static int binarySearch(double [] array, double find){
        int first = 0;
        int last = array.length;
        int mid = (first   last ) / 2;
        while(first <= last){
            if(array[mid] < last){
                first = mid  1;
            }else if(array[mid] == find){
                return mid;
            }else{
                last = mid -1;
            }
            mid = (first   last) / 2;
        }
        if(first > last){
            return -1;
        }
        return -1;
    }
}   

How it is supposed to work that it takes the array of doubles and a random number to find if the number is in the array, if it is returns the index, if its not in the array, it returns -1. I have a linear search method that works but for some reason this won't work. Thank you

CodePudding user response：

Array index out of bound means you are trying to access the array element which is not within the array.
In Java array.length gives you the size of an array.
But elements of an array are identified by the index and index value starts from 0.
Which means that first element of an array has the index = 0 and the last element has the index = array.length(size) - 1.

In your code of binary search, you are taking int last = array.lenght which is wrong.
It should be int last = array.length - 1

CodePudding user response：

public static void main(String[] args) {
    double[] arr = new double[9999];
    Random random = new Random();

    for (int i = 0; i < arr.length; i  )
        arr[i] = random.nextDouble() * 9_999;

    Arrays.sort(arr);
    System.out.println(binarySearch(arr, random.nextDouble() * 9_999));
}

public static int binarySearch(double[] arr, double find) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo   1 < hi) {
        int mid = (lo   hi) / 2;
        int res = Double.compare(find, arr[mid]);

        if (res == 0)
            return mid;
        if (res < 0)
            hi = mid;
        else
            lo = mid;
    }

    if (Double.compare(find, arr[lo]) == 0)
        return lo;
    if (Double.compare(find, arr[hi]) == 0)
        return hi;

    return -1;
}