Index out bound error when I try doing a binary search through the array

Question

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

Kashinath · Accepted Answer · 2022-10-28 20:04:32Z

1

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

answered Oct 28, 2022 at 20:04

Kashinath

1864 bronze badges

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

Comments

Oleg Cherednik · Accepted Answer · 2022-10-28 19:33:05Z

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;
}

Collectives™ on Stack Overflow

Index out bound error when I try doing a binary search through the array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related