I have an array in which seven numbers are sorted from the smallest to the biggest. I have to write a recursive function that returns the index of a specific value. I am not allowed to use while or for loops. I have absolutely no approach and do not know how to solve this. Can you give me some ideas?
1
-
3a binary searchQuentinUK– QuentinUK2018-11-24 23:33:58 +00:00Commented Nov 24, 2018 at 23:33
Add a comment
|
2 Answers
Since the array is sorted, the question probably wants you to use binary search rather than a linear search approach. Look up "recursive binary search". It should help you with your problem.
Sample code from http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html:
int rBinarySearch(int sortedArray[], int first, int last, int key) {
// function:
// Searches sortedArray[first]..sortedArray[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -(index where it could be inserted)-1.
// parameters:
// sortedArray in array of sorted (ascending) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -insertion_position -1
// if key is not in the array.
if (first <= last) {
int mid = (first + last) / 2; // compute mid point.
if (key == sortedArray[mid])
return mid; // found it.
else if (key < sortedArray[mid])
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key);
}
return -(first + 1); // failed to find key
}
6 Comments
Arthur Johnson
Thank you very much, the problem is I am only allowed to give three things to the function: the sorted array. the value that is looked for and the size of the array. That make`s this task very complicated
@ArthurJohnson, in that case, I think this thread may help you stackoverflow.com/questions/8392637/… it is in java, but the logic should be easily transferable.
PaulMcKenzie
That make`s this task very complicated -- It really doesn't. The first argument could be the pointer to a sorted sequence of values -- it doesn't matter if the pointer is in the middle of the original sorted array, the beginning of the original sorted array, etc -- it's just a pointer to a series of sorted values. The issue with this answer is that each recursive call always passes the beginning of the original array each time. Just change that deficiency, and you basically have the answer.
Arthur Johnson
Thank You Paul, but what do you mean with recursive call always passes the beginning of the original array each time. How can I make the function start with another place in the array with each call
PaulMcKenzie
@ArthurJohnson Look at it conceptually -- on each iteration, half of the original array is "thrown away" -- there is no need (as in the answer's code is doing) of passing a pointer to the entire array each and every time, since half of it is discarded and not part of the search. So just pass the beginning of the part of the array that is still being used in the search, and throw away the
first and last parameters and replace with the appropriate size parameter. Doing this satisfies all of the requirements you stated. |
Given the function signature:
int search(int *sorted, int value, unsigned size)
We first test if size is 1, as that's our base case. If size is one, we check that one element, sorted[0], to see if it equals the value we're looking for. If it does, return 0, the (only) index. If it doesn't return -1 to indicate "not found".
If size is greater than one, we continue on. First we calculate half which is size / 2. Then we call ourselves recursively with that diminished size:
result = search(sorted, value, half);
if this result isn't -1 , return it as it's the index we want. If result is -1, we continue on. We again call ourselves recursively but this time with the other half of the array we didn't test earlier:
result = search(sorted + half, value, size - half);
if result is not -1, then we return result plus the half size. If result is -1, then simply return -1 as the value isn't in the array.
