Linear Search: the recursive way.

This is a discussion on Linear Search: the recursive way. within the C Programming forums, part of the General Programming Boards category; helo, I want to modify a linear Search program which is currently using a loop to search for a number ...

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Linear Search: the recursive way.

    helo,

    I want to modify a linear Search program which is currently using a loop to search for a number in an array to a recursive one. But don't know where to start. Pls direct. Thnx in advance. The current iterative version of linearSearch is :

    Code:
    #include <stdio.h>
    #define SIZE 100
    
    int linearSearch( const int [], int, int );
    
    int main()
    {   
       int a[ SIZE ], x, searchKey, element;
    
       for ( x = 0; x <= SIZE - 1; x++ )  /* create data */
          a[ x ] = 2 * x;
    
       printf( "Enter integer search key:\n" );
       scanf( "%d", &searchKey );
       element = linearSearch( a, searchKey, SIZE );
    
       if ( element != -1 )
          printf( "Found value in element %d\n", element );
       else
          printf( "Value not found\n" );
    
       return 0;
    }
    
    int linearSearch( const int array[], int key, int size )
    {
       int n;
    
       for ( n = 0; n <= size - 1; ++n )
          if ( array[ n ] == key )
             return n;
    
       return -1;
    }
    To modify this code to recursive, i can pass two arguments to the function: 1. integer array 2. size of the array
    Is it possible? Pls show.
    Last edited by Nutshell; 01-12-2002 at 10:27 AM.

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    Somethnig like -

    Code:
    int linearSearch( const int array[], int key, int size )
    {
    	int ret =-1;
    	if (array[0]==key)
    		ret=key;
    	else
    		if(size>0)
    			ret = linearSearch(&array[1],key,size-1);
       
    	return ret;
    }

  3. #3
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    sorry i forgot to mention. I have the return the array subscript in which the searchkey is found, not the actual search key. Thats what troubling me.

    thnx

  4. #4
    Unregistered
    Guest
    Here's Sorensen's code modified to return the index of the array instead of the key.
    Code:
    int linearSearch( const int array[], int key, int size, int i )
    {
      int ret = -1;
      if (array[i] == key)
        ret = i;
      else
        if(size > 0){
          ret = linearSearch(array, key, size - 1, ++i);
        }
       
      return ret;
    }

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Hi but i can only use two parameters: the array and its size and thats it?

    is it possible ?

    thnx

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    *shrug* sure....
    Code:
    int linearSearch(const int array[], int key, int size)
    {
     if (size == 0) return -1;
     else if (array[size - 1] == key) return size - 1;
     else return linearSearch (array, key, size - 1);
    }
    Really, it might be easier to just have a wrapper function, or macro, which just takes care of tossing in the extra value instead of writing a function that doesn't use it.

    This function that I've got basically starts at the back of the array and works up to the top. It's possible to go the other way with just 2 args, but it's a little more complicated if you want to handle the case where the element is not in the array.
    Callou collei we'll code the way
    Of prime numbers and pings!

  7. #7
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    thnx thats clever

    but can you also show me to go from the beginning instead of doing from the back up?

    I wanna learn.
    Last edited by Nutshell; 01-14-2002 at 05:23 AM.

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Like I said, doing it from the front is a bit more complicated, although the steps are basically going to be the same, now it involves checking recursive return and pointer arithmatic. Interestingly, the check could be tossed out if instead of using the invalid return -1, we use the invalid return size (since there is no array[size] in an array of size elements).

    int linearSearch(const int array[], int key, int size)
    returns the index of the first occourance of key

    1) if size = 0, return error
    2) if the first element of the array is it, then return 0
    3) otherwise, check the array starting at the next element
    and return 1 + the answer from that
    3b) handle error

    Code:
    int linearSearch(const int array[], int key, int size)
    {
     int n;
     if (size == 0) return -1;
     if (*array == key) return 0;
     n = linearSearch (array + 1, key, size - 1);
     if (n != -1) n ++;
     return n;
    }
    For the sake of explanation, I'm gonna go ahead and step through this.
    Code:
    int main (void)
    {
     int x;
     int array [] = {3, 8, 2, 6, 9};
     x = linearSearch (array, 2, 5};
     return 0;
    }
    Code:
    x = linearSearch ({3 8 2 6 9}, 2, 5);
      size != 0, *array != key, so we search the array {8 2 6 9}
      n = linearSearch({8 2 6 9}, 2, 4);
        size != 0, *array != key, so we search the array {2 6 9}
        n = linearSearch({2 6 9}, 2, 3);
          size != 0, but *array == key, so key is the 0 element of this
          array, so we return 0
        n = 0; key was the 0th element of {2 6 9}, so it's the 0 + 1
        element of this array (1)
        so we return 1
      n = 1; key was the 1st element of {8 2 6 9}, so it's the 1 + 1
      element of this array (2)
      so we return 2
    x = 2;
    Last edited by QuestionC; 01-15-2002 at 03:18 AM.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 06:20 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. linear search for structure (record) array
    By jereland in forum C Programming
    Replies: 3
    Last Post: 04-21-2004, 08:31 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21