ArrayIndesOutOfBoundsException in custom binary search?

Question

I am trying to implement binary search in Java:

import java.util.Scanner;

public class Search 
{
public static void sequential_search(int[] array,int search_variable)
{
    boolean flag = false;
    for(int loop=0;loop<array.length;loop++)
    {
        if(array[loop] == search_variable)
        {
            flag = true;
            break;
        }
    }
    if(flag == true)
        System.out.println("The value is present");
    else
        System.out.println("The value is absent");
}

public static int binary_search_recursive(int[] array,int low,int high,int search_variable)
{
    if(low > high)
    {
        return 0;
    }
    else
    {
        int mid;
        mid = (low+high)/2;
        if(array[mid] == search_variable)
        {
            return 1;
        }
        else if (array[mid] > search_variable)
        {
            return binary_search_recursive(array, low, mid - 1, search_variable);
        }
        else 
        {
            return binary_search_recursive(array, mid + 1, high, search_variable);
        }
    }
}

public static void main(String[] args) 
{
    int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int search_variable;

    System.out.println("Please enter the number to be search:");
    Scanner number = new Scanner(System.in);
    search_variable = number.nextInt();
    System.out.println("The number to be searched is "+search_variable);

    //sequential_search(array,search_variable);

    if ((binary_search_recursive(array, 0, array.length, search_variable)) == 0)
        System.out.println("The value is present");
    else
        System.out.println("The value is absent");

}

}

I'm just getting confused while I'm getting out of ArrayOutOfBoundsException, when I enter a term which is not found by the algorithm.

Please enter the number to be search:
12
The number to be searched is 12
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
    at Search.binary_search_recursive(Search.java:32)
    at Search.binary_search_recursive(Search.java:42)
    at Search.binary_search_recursive(Search.java:42)
    at Search.binary_search_recursive(Search.java:42)
    at Search.main(Search.java:59)

Any input on this would be helpful. Thanks :)

Please add line numbers. What is on lines 32 and 42 ?

Thilo
– Thilo

2012-03-11 07:04:19 +00:00
Commented Mar 11, 2012 at 7:04 — Thilo
– Thilo, Commented Mar 11, 2012 at 7:04
Did you try to debug this using a debugger?

home
– home

2012-03-11 07:04:26 +00:00
Commented Mar 11, 2012 at 7:04 — home
– home, Commented Mar 11, 2012 at 7:04

templatetypedef · Accepted Answer · 2012-03-11 07:04:11Z

I think that the issue here is that your low and high variables represent the range [low, high), with the high value excluded. This means that your base case, which is currently

if(low > high)
{
    return 0;
}

should probably be

if(low >= high)
{
    return 0;
}

Since if you have the range [low, low), there aren't any elements left. Requiring low > high before you terminate means that you will need low to actually exceed high, which shouldn't be possible.

If I'm correct about this, this also means that one of your recursive calls to the function has the wrong upper bound. Specifically, this code:

    else if (array[mid] > search_variable)
    {
        return binary_search_recursive(array, low, mid - 1, search_variable);
    }

should be

    else if (array[mid] > search_variable)
    {
        return binary_search_recursive(array, low, mid, search_variable);
    }

since if high is exclusive, passing in mid as the upper bound is the proper way to get everything up to but not including the middle value.

Hope this helps!

DanRedux · Accepted Answer · 2012-03-11 07:06:29Z

0

if ((binary_search_recursive(array, 0, array.length, search_variable)) == 0)

You eventually are checking array[array.length] if you use those arguments. 10 elements means array.length is 10, but the 10th index is of course undefined.

if ((binary_search_recursive(array, 0, array.length-1, search_variable)) == 0)

answered Mar 11, 2012 at 7:06

DanRedux

9,4096 gold badges25 silver badges41 bronze badges

Collectives™ on Stack Overflow

ArrayIndesOutOfBoundsException in custom binary search?

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