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.

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);

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.

>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

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?

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

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.