pset3: search (am I in the right track??)

Question

bool search(int value, int values[], int n)

//search for middle lists

if (value == values [n / 2])

{

return 1;

}

//number greater search left

else if ( value > values[n / 2 ])

{

search(int value, int values[n / 2] - 1, int n)

}

//number smaller search right else if (value < values[n / 2 ])

{

search( int value, int values[n / 2] + 1, int n)

}

return 0; }

Answer 1

So you want to use recursion.

First, recursion needs an end criterion, some case of base case. Finding the element is one, but empty array should be another. if (n <= 0) { return false; } could be a good idea for the top of your function, before you access any array element.

You then would need to pass the result of the called function to the calling function. You could do this by using

return search(value, &values[n/2+1], n-n/2-1);

and

return search(value, values, n/2);

Note that due to truncation when dividing integers, n-n/2 is not the same as n/2, more like (n+1)/2 for positive numbers.

An alternative to this recursion would be a loop, where you kept track of the current search interval, and in each iteration determined the middle of the interval, and updated one of the interval boundaries based on that middle element. That loop would then run as long as the search interval has elements to test.