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

    Join Date
    Jul 2002
    Location
    Tallahassee
    Posts
    55
    Rep Power
    14

    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.

    I got the last two tests correct, just not the first one. Please help.

    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. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,646
    Rep Power
    4248
    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!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2002
    Location
    Tallahassee
    Posts
    55
    Rep Power
    14
    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.
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,646
    Rep Power
    4248
    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! :)
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2002
    Location
    Tallahassee
    Posts
    55
    Rep Power
    14

    Unhappy 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?
  10. #6
  11. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,646
    Rep Power
    4248
    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 :)

IMN logo majestic logo threadwatch logo seochat tools logo