When i try to run the below Binary Search code in java, it throws ArrayOutOfExcepetion. Can any anyone have a look and tell me where I went wrong?

Question

It throws error ArrayIndexOutOfBound, when i try to search an element which is out of the range of given input array.

Below is the code snippet:

import java.util.*;

public class Binary {
    int binSearch(int arr[], int target)
    {
        int low=0;
        int high= arr.length;
        while(low<=high)
        {
            int mid = (low+high)/2;              
            if(arr[mid] == target)
                return mid;             
            if(target>arr[mid])
                low=mid+1;              
            else
                high=mid-1;                         
         }          
         return -1;
    }

    public static void main(String arg[])
    {
        Binary b= new Binary();
        int arr[]= {2, 4, 5, 7, 23, 31, 34, 43, 45};            
        int ans=b.binSearch(arr, 46);           
        if(ans==-1)
            System.out.println("The element is not found");         
        else
            System.out.println("Element is found at postion = " + (ans+1));
    }
}

Sarim Sidd · Accepted Answer · 2015-12-25 07:08:28Z

2

Array length is the total count of elements in the array, but since the index starts from 0, the last value you can access from the array is always length - 1, In your code above, you are running the loop from 0 to the length of array, which I believe is the problem here.

So try something like

int binSearch(int arr[], int target)
{
    int low=0;
    int high= arr.length -1; //Correct condition

    while(low<=high)   //Correct condition
    {
        int mid = (low+high)/2;

        if(arr[mid] == target)
            return mid;

        if(target>arr[mid])
            low=mid+1;

        else{
            high=mid-1;
          }

    }

    return -1;
}

Hope it helps

edited Dec 25, 2015 at 7:08

answered Dec 25, 2015 at 6:45

Sarim Sidd

2,1762 gold badges22 silver badges31 bronze badges

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

2 Comments

Sarim Sidd Over a year ago

Glad to hear it helped you, please take a moment to mark the answer correct (click the tick next to question). Thanks

Yogesh D Over a year ago

Could you please also upvote my question as I am being locked out of asking more question. Thanks!

Moon · Accepted Answer · 2015-12-25 06:51:11Z

2

Your setting your high larger than your max array index.
Set the initial value to the largest allowed index as the length - 1, like this:

int binSearch(int arr[], int target)
{
    int low=0;
    int high= arr.length-1;

    while(low<=high)
    {
        int mid = (low+high)/2;

        if(arr[mid] == target)
            return mid;

        if(target>arr[mid])
            low=mid+1;

        else{
            high=mid-1;
            }

    }

    return -1;
}

answered Dec 25, 2015 at 6:51

Moon

1,1512 gold badges11 silver badges25 bronze badges

2 Comments

Moon Over a year ago

Fantastic. Please mark the answer as accepted when you have a sec. And have a Merry Christmas.

Yogesh D Over a year ago

Sure. Thanks! +1! Could you please also upvote my question as I am being locked out of asking more question.

Collectives™ on Stack Overflow

When i try to run the below Binary Search code in java, it throws ArrayOutOfExcepetion. Can any anyone have a look and tell me where I went wrong?

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related