CODEWITHSUNDEEP
javaarraysalgorithmsearchbinary
Abdulla Dlshad
Abdulla Dlshad

Reputation: 141

Binary Search gives Index Out of Bound Exception in Java

I am trying to implement binary search using java programming language. it's obvious that the array should be sorted in order to make use of binary search because it uses divide and conquer concept. The code works fine for both cases when the when the element is within the array and when it's not. But, when I enter a number that is greater than the greatest number inside the array, the program will crash and give Index Out Of Bound Exception.

public class Binary {

public static void search(int arr[]) {
    Scanner in = new Scanner(System.in);
    int upper = arr.length;
    int lower = 0;
    int middle = 0;
    int flag = 0;
    int key;

    /*
     * flag = 0 ---> not found yet.
     * flag = 1 ---> element is found.
     * flag = 2 ---> no such element.
     */

    System.out.println("Enter the number that you want to find... ");
    key = in.nextInt();

    while (flag == 0) {
        middle = (int) (lower + upper) / 2;

        if (key == arr[middle]) {
            flag = 1;
        }

        if (key < arr[middle]) {
            upper = middle - 1;
        } else if (key > arr[middle]) {
            lower = middle + 1;
        }
        if (lower > upper) {
            flag = 2;
        }
    }
    if (flag == 1) {
        System.out.println(arr[middle] + " has been found, its index is: "
                + middle);
    } else
        System.out.println("Error, no such element.");
}

public static void main(String[] args) {

    int arr[] = { 2, 4, 6, 8, 11, 34, 56 };
    search(arr);
}

}

Upvotes: 1

Views: 1948

Answers (2)

M Oehm
M Oehm

Reputation: 29126

You can take MisterDev's solution and correct the upper bound. Usually, in Java arrays, the lower bound is inclusive and the upper bound exclusive, however, and I like the idea that lower and upper follow this pattern.

Then, lower < upper means that the range isn't empty and the middle point will become the new exclusive upper bound when searching continues in the first half:

public static int search(int arr[], int key)
{
    int upper = arr.length;
    int lower = 0;

    while (lower < upper) {
        int middle = (lower + upper) / 2;

        if (key == arr[middle]) return middle;

        if (key < arr[middle]) {
            upper = middle;
        } else if (key > arr[middle]) {
            lower = middle + 1;
        }
    }

    return -1;
}

I've made the function take the key as a parameter and return the index or -1 if the key isn't found. Taking user input and the flag have no business in your code, in my opinion; you should write a wrapper for that, so that Binary.search really just does the search.

Upvotes: 1

Devid Farinelli
Devid Farinelli

Reputation: 7544

This should solve your problem

int upper = arr.length-1;

If you are looking for a number greater than the greatest, than you will sure look at the last element of the array. But in your code upper has an initial value that is 1 more than the index of the last element.

Upvotes: 2

Related Questions