Find value in array with recursion

Question

I am trying to find a value in an array with a specific method.

public void findElement(int valueToFind)
{
    FindElementInArray(valueToFind, 0, _array.Length - 1);
}

public void FindElementInArray(int value, int lb, int rb)
    {          
        int currIndex = (rb - lb) / 2;
        if (_array[currIndex] == value)
        {
            //Value found
            Console.WriteLine("Value found");
            return;
        }

        //If found value is smaller than searched value
        else if (_array[currIndex] < value)
        {
            FindElementInArray(value, currIndex+1, rb);
        }

        //If found value is bigger than searched value
        else
        {
            FindElementInArray(value, lb, currIndex - 1);
        }

So I search the middle of the array, if the value is bigger than the value we look for, we search the middle of the left half and so on...

But it doesnt find some values even if they are in the array. Can someone see a mistake?

Is your input array sorted? Because it has to be if binary search should work — Philipp Sch
– Philipp Sch, Commented Apr 10, 2013 at 9:57
Without actually looking at the code: have you made sure your array is sorted? — nvoigt
– nvoigt, Commented Apr 10, 2013 at 9:58

Daniel Imms · Accepted Answer · 2013-04-10 10:10:02Z

6

You're using the index wrong.

int currIndex = (rb - lb) / 2;

You need to get the middle point of rb and lb which would be:

int currIndex = lb + (rb - lb) / 2;
// or
// int currIndex = (lb + rb) / 2;

You will also need an exit out of the recursion somehow if the value isn't present because currently it will just go on and cause a stack overflow. You could do that by checking to ensure lb and rb are different for example:

if (_array[currIndex] == value)
{
    //Value found
    Console.WriteLine("Value found");
    return;
}
else if (lb != rb)
{
    //If found value is smaller than searched value
    else if (_array[currIndex] < value)
    {
        FindElementInArray(value, currIndex+1, rb);
    }

    //If found value is bigger than searched value
    else
    {
        FindElementInArray(value, lb, currIndex - 1);
    }   
}

edited Apr 10, 2013 at 10:10

answered Apr 10, 2013 at 9:59

Daniel Imms

50.6k19 gold badges157 silver badges170 bronze badges

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

2 Comments

Daniel Imms Over a year ago

@TimKatheteStadler Np, I updated the answer again, you need to exit the recursion somehow. Make sure you accept the answer by hitting the tick :)

Dariusz Over a year ago

lb + (rb - lb) /2 == (lb + rb) / 2

Zdeslav Vojkovic · Accepted Answer · 2013-04-10 10:00:41Z

0

int currIndex = (rb - lb) / 2;

should be

int currIndex = (rb + lb) / 2;

You need to find a midpoint.

answered Apr 10, 2013 at 10:00

Zdeslav Vojkovic

14.7k37 silver badges45 bronze badges

Collectives™ on Stack Overflow

Find value in array with recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related