Thread: Please check the bug in this one

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Please check the bug in this one

    Hey all,
    These are my two search algorithms: recursive binary and recursive sequential search.
    For some reason I am not getting the right output
    Code:
    //'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);
    }
    
    int binarySearch(int item, int *list, int listSize) {
       if (listSize == 0) {
         return -1;
       }
       else{
           int mid = (listSize) / 2;  // compute mid point.
           list = list + mid;
           if (item == *list) 
               return *list;   // found it.
           else if (item < *list) 
               // Call ourself for the lower part of the array
               return binarySearch(item, list, listSize - 1);
           else
               // Call ourself for the upper part of the array
               return binarySearch(item, list, listSize + 1);
       }
    }
    This program should gimme the position of a number(item) in the array that I pass(*list). It also must use pointers and recursion to get credit. I am baffled as well as stressed. Please tell me if I am missing something. Thanks again guys.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    A binary search is supposed to divide the size by 2 each time
    It also assumes that the list is sorted (if it isn't a binary search will randomly fail/pass)

    So
    Code:
           else if (item < *list) 
               // Call ourself for the lower part of the array
               return binarySearch(item, list, listSize - 1);
           else
               // Call ourself for the upper part of the array
               return binarySearch(item, list, listSize + 1);
    Should be something like
    Code:
           int mid = (listSize) / 2;  // compute mid point.
           if (item == list[mid]) 
               return list[mid];   // found it.
           else if (item < list[mid]) 
               // Call ourself for the lower part of the array
               return binarySearch(item, list, listSize/2);
           else
               // Call ourself for the upper part of the array
               return binarySearch(item, list+mid, listSize/2);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    Wow! Thank you so much for the binary.... with a little bit more modification it worked perfectly! Could you tell what is happening to the recursive sequential search though? I am not getting the answer that I need. Please help... I really wouldn't be pleading with ya if I didn't have two programs due tonight at midnight! Thank you.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Could you tell what is happening to the recursive sequential search though?
    It's crazy, try this instead:
    Code:
    int ssearch ( const int *list, const int find, int index, const int size )
    {
      if ( index < size ) {
        if ( *list != find )
          index = ssearch ( list + 1, find, index + 1, size );
      }
    
      return index;
    }
    Here I am doing recursion again Salem, is this a new trend?

    -Prelude
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Only one problem

    Hey Code Goddess,
    There is only one minor problem though. I MUST HAVE EXACTLY three parameters for the sequential search. Man, I was soo excited a couple of minutes ago... Is there a way that this is possible?

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Provided you place a sentinel value at the end of the array, you can do this:
    Code:
    int ssearch ( const int *list, const int find, int index )
    {
      if ( *list != SENTINEL && *list != find )
        index = ssearch ( list + 1, find, index + 1 );
    
      return index;
    }
    Another option is a bit hackish, but it works:
    Code:
    int ssearch ( const int *list, const int find, int index )
    {
      int n = 0;
    
      if ( index >= 0 ) {
        if ( *list != find ) {
          n += 1;
          n += ssearch ( list + 1, find, index - 1 );
        }
      }
    
      return n;
    }
    -Prelude
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    just a bit more...

    CodeGoddess,
    You are da bomb. Only one more condition remains.... I took the second 'hackish' looking piece of code and it works in every case except where the element we are lookin for cannot be found in the array. We need to return a -1 if the element is not in the array. Anyway of doing that? I know I am just sucking you dry at this point but I am at the eleventh hour and I will be eternally grateful.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. gaks bug?
    By Yarin in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 08-31-2008, 02:47 PM
  2. Debugging a rare / unreproducible bug..
    By g4j31a5 in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 08-05-2008, 12:56 PM
  3. Check application visibility
    By 3saul in forum Linux Programming
    Replies: 2
    Last Post: 02-13-2006, 05:13 PM
  4. spell check in C using a dictionary file
    By goron350 in forum C Programming
    Replies: 10
    Last Post: 11-25-2004, 06:44 PM
  5. MFC: How do you check if a directory exists before creating?
    By BrianK in forum Windows Programming
    Replies: 5
    Last Post: 07-06-2004, 01:09 AM