Thread: Two Recursively Searching Algorithms - and one really annoying bug!

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2002
Location
Tallahassee
Posts
55
Rep Power
17

Two Recursively Searching Algorithms - and one really annoying bug!

Hey all,
I have a problem with a recursive algorithm. I actually need help with two of them:
One is the recursive sequential search and the other is the recursive binary search. I am about to place a lot of code on the screen so watch out now.
Code:
```#include "hw4Lib.h"
#include <string>

void printArray(int* array, int arraySize)
{
cout << "[";
for (int i = 0; i < arraySize - 1; i++)
{
cout << array[i] << ", ";
}
cout << array[arraySize - 1] << "]";
}

int main()
{
int unsortedList[8] = {3, 8, 5, 7, 2, 1, 4, 6};
int unsortedList2[7] = {3, 8, 5, 7, 2, 1, 4};
//int sortedList[8] = {1, 2, 3, 4, 5, 6, 7, 8};
//int sortedList2[7] = {1, 2, 3, 4, 5, 6, 7};
int item1 = 7;
int item2 = 4;
int item3 = 9;
int arraySize = 8;
int arraySize2 = 7;

cout << "sequentialSearch(" << item2 << ", ";
printArray(unsortedList2, arraySize2);
cout << ", " << arraySize2 << ") = ";
cout << sequentialSearch(item2, unsortedList2, arraySize2) << "\n";

cout << "sequentialSearch(" << item1 << ", ";
printArray(unsortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << sequentialSearch(item1, unsortedList, arraySize) << "\n";

cout << "sequentialSearch(" << item3 << ", ";
printArray(unsortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << sequentialSearch(item3, unsortedList, arraySize) << "\n\n";

//cout << "binarySearch(" << item2 << ", ";
//printArray(sortedList2, arraySize2);
//cout << ", " << arraySize2 << ") = ";
//cout << binarySearch(item2, sortedList2, arraySize2) << "\n";

//cout << "binarySearch(" << item1 << ", ";
//printArray(sortedList, arraySize);
//cout << ", " << arraySize << ") = ";
//cout << binarySearch(item1, sortedList, arraySize) << "\n";

//cout << "binarySearch(" << item3 << ", ";
//printArray(sortedList, arraySize);
//cout << ", " << arraySize << ") = ";
//cout << binarySearch(item3, sortedList, arraySize) << "\n";
}```
The above is the driver. Below is the recursive sequential search that I got so far.
Code:
```#include "hw4Lib.h"

//'listSize' is a parameter that inputs size of the array into function
//'item' is a parameter that inputs the current value of the function
//list is a pointer to the array

int sequentialSearch(int item, int *list, int listSize)
{
if (listSize == 0)
return -1;
if (*list == item)
return listSize - 2;
else
list++;
return sequentialSearch(item, list, listSize - 1);
}```
And below is my hw4Lib.h. Yes, this is for one of my courses but hey you gotta gimme an A for trying and I am so close too.
Code:
```#include <iostream.h>

int sequentialSearch(int item, int* list, int listSize);
int binarySearch(int item, int* list, int listSize);```
It almost works guys... I just can't get it to read the right answers for the first sequential_search. OOps almost forgot what the answer should be This program basically searches for a specific integer and the answer would be whatever position the integer is in (starting from 0 of course..) If the integer is not in the array then it should print out a -1.

And just to make things a little bit more challenging I need to do the binary search also. Any help at all would be appreciated. I thank you all in advance.
2. Here's one way for the sequential search:
Change sequentialSearch to accept a fourth param, the full size of the array.
Code:
```int int sequentialSearch(int item, int *list, int listSize, int fullSize)
{

if (listSize == 0)
return -1;
if (*list == item)
return fullSize - listSize;
else
list++;
return sequentialSearch(item, list, listSize - 1, fullSize);
}```
and in function main(), change the calls to
Code:
```  cout << "sequentialSearch(" << item2 << ", ";
printArray(unsortedList2, arraySize2);
cout << ", " << arraySize2 << ") = ";
cout << sequentialSearch(item2, unsortedList2, arraySize2, arraySize2) << "\n";

cout << "sequentialSearch(" << item1 << ", ";
printArray(unsortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << sequentialSearch(item1, unsortedList, arraySize, arraySize) << "\n";

cout << "sequentialSearch(" << item3 << ", ";
printArray(unsortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << sequentialSearch(item3, unsortedList, arraySize, arraySize) << "\n\n";```
Note that I made sequentialSearch return the index of a 0 based array (since you're returning -1 on failure). Hope this helps!
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2002
Location
Tallahassee
Posts
55
Rep Power
17
THANK YOU SO MUCH FOR ALL THOSE WHO HELPED! I GOT IT DONE!(Sorry about the caps) but I am just so blasted excited! There's nothing like the feeling that comes over you when you program compiles from scratch...nothing can beat it. Thank again.
4. Here's my implementation of binarySearch:
Code:
```int binarySearch(int item, int *list, int listStart, int listEnd)
{
int midPoint = (listStart + listEnd) / 2;
if (*(list + midPoint) == item)
return midPoint;
else if (midPoint == listStart)
return -1;
else if (*(list + midPoint) < item)
return binarySearch(item, list, midPoint, listEnd);
else if (*(list + midPoint) > item)
return binarySearch(item, list, listStart, midPoint);
}```
Change the calls in main() to:
Code:
```  cout << "binarySearch(" << item2 << ", ";
printArray(sortedList2, arraySize2);
cout << ", " << arraySize2 << ") = ";
cout << binarySearch(item2, sortedList2, 0, arraySize2) << "\n";

cout << "binarySearch(" << item1 << ", ";
printArray(sortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << binarySearch(item1, sortedList, 0, arraySize) << "\n";

cout << "binarySearch(" << item3 << ", ";
printArray(sortedList, arraySize);
cout << ", " << arraySize << ") = ";
cout << binarySearch(item3, sortedList, 0, arraySize) << "\n";```
and change the prototypes in hw4Lib.h to
Code:
```int sequentialSearch(int item, int* list, int listSize, int fullSize);
int binarySearch(int item, int* list, int listStart, int listEnd);```
Hope this helps! :)
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2002
Location
Tallahassee
Posts
55
Rep Power
17

A little problem...

There seems to be a problem. I read back on the program requirements and it seems like the only files that can be edited is the hw4Lib.cpp and hw4Lib.h which means that I cannot change the other files. Is there any way to get around this and retain the same functionality?
6. I can think of a couple of ways at least. Before I come up with solutions though, can you please verify a few things for me:
1. Do these functions have to be recursive.
2. Can these functions call other functions (i.e.) can I write:
int sequentialSearch2(int item, int *list, int listSize, int fullSize)
and then make sequentialSearch call sequentialSearch2 like this:
int sequentialSearch(int item, int *list, int listSize) {
return sequentialSearch2(item, list, listSize, listSize);
}
This way, main() does not need to be modified at all :)
3. Are you allowed use other C++ features such as default parameter values for functions?
4. Can you do creative things with #define. Specifically, what if you do something like this in hw4Lib.h
#define sequentialSearch(a, b, c) sequentialSearch2(a, b, c, c)
This way, you're not altering the file containing main() directly, but since hw4Lib.h is #included in the file containing main(), you are using the C pre-processor to alter the code for you.

There's more than one way to get around not modifying the file containing main(), depending on how you want to bend the rules :)