CODEWITHSUNDEEP
c++arraysrecursionsearch
Arthur Johnson
Arthur Johnson

Reputation: 21

find element in sorted array without using for or while

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?

Upvotes: 0

Views: 529

Answers (2)

cdlane
cdlane

Reputation: 41872

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.

Upvotes: 0

user8109196
user8109196

Reputation:

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
}

Upvotes: 1

Related Questions