binary search algorithm implementation causes stackoverflow error

hi,

I am trying to learn how to write recursive functions.

Here, I tried to create a recursive implementation of binary search algorithm. The algorithm works fine but when the number of elements to search is increased(say 35 elements) a stackoverflowerror exception is raised.

here is the code.

Code:

---

package algorithms;

public class BinarySearch {
    int len;
    int[] inputs;
    int search_element;
    int elementfoundatindex;
    public void setInputs(int[] ip)
    {
        len = ip.length;
        inputs = new int[len];
        inputs = ip;
    }
    public void setSearch_element(int se)
    {
        search_element = se;
    }
    public int BinarySearchAlgorithm(int prev_index)
    {
        if(search_element == inputs[inputs.length-1])
            return inputs.length-1;
        if(search_element == inputs[0])
            return 0;
        if(prev_index < 0 || prev_index > len)
        {
            return -1;
        }
        else
        {
            if(search_element == inputs[prev_index])
            {
                return prev_index;
            }
            else if(search_element > inputs[prev_index])
            {
                return BinarySearchAlgorithm(prev_index + (int) ((double) prev_index/2.0));
            }
            else if(search_element < inputs[prev_index])
            {
                return BinarySearchAlgorithm((int) ((double) prev_index/2.0));
            }
            else
            {
                return -9;
            }
        }
    }
}

---

the class and its member variables get their values from textboxes in a JFrame (which also calls the BinarySearchAlgorithm() on a onclick event for a button).

kindly suggest me ways of making this implementation work for large number of elements.

You could increase the maximum heap size. To do this pass the switch -Xmx(size) to the JVM ie

java -Xmx512m myApp

Sets the max heap to 512Mb.

How do you test the code? What is the value of the arg for the search method?

Quote:

---

Originally Posted by creeping death

kindly suggest me ways of making this implementation work for large number of elements.

---

It's virtually impossible for a properly written recursive binary search to cause a call stack overflow and certainly not with just 35 elements. The stack requirement grows logarithmically with the number of elements. Say the call stack can handle 100 recursive calls (normal would be in the thousands). This would allow the binary search to handle 2^100 (in the order of 10^30) elements without overflowing, a gigant number.

So the stack overflow indicates something is wrong with your implementation and increasing the stack is not the solution.

A quick inspection gives a hint. A proper recursive binary search takes two arguments representing a range. Yours takes only one so it cannot be correct. I suggest you locate a Java implementation on the internet and modify it to your needs. There are plenty.

Note that a binary search only works if the elements are sorted. Otherwise it will fail even if it's correctly implemented.

apparently my logic was incorrect. i modified the implementation based on reference on the internet. the correct implementation was able to search form a set of 99999 elements in 12 milliseconds.

the correct implementation is:

Code:

---

public int BinarySearchAlgorithm(int minbound,int maxbound)
    {
        int prev_index=(minbound+maxbound)/2;
        if(search_element == inputs[inputs.length-1])
            return inputs.length-1;
        if(search_element == inputs[0])
            return 0;
        if(minbound > maxbound)
        {
            return -1;
        }
        else
        {
            if(search_element == inputs[prev_index])
            {
                return prev_index;
            }
            else if(search_element > inputs[prev_index])
            {
                return BinarySearchAlgorithm(prev_index+1,maxbound);
            }
            else if(search_element < inputs[prev_index])
            {
                return BinarySearchAlgorithm(minbound,prev_index-1);
            }
            else
            {
                return -9;
            }
        }       
    }

---

:-)

Quote:

---

Originally Posted by creeping death

the correct implementation was able to search form a set of 99999 elements in 12 milliseconds.

---

It sounds a little slow. 99999 elements is just in the order of 15 accesses until the binary search finds the element.

The algorithm may still be flawed but a more likely reason is the way you measure performance.

Since timing in Java has a resolution of milliseconds the algorithm may be much faster than the timing suggests. The best approach is to measure how long it takes for the algorithm to run repeatedly, say 1000 times. Then you divide the time it took with 1000 to get the average performance of the algorithm. You should make several such runs in a row say 10. This gives Java a chance to make runtime optimizations.

I also suggest you compare the binary search with how long it takes to visit all elements linearly in a loop. This will give an indication as to whether the binary search works properly.