14 Replies - 30128 Views - Last Post: 01 April 2008 - 05:13 PM Rate Topic: -----

#1 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Recursive Binary Search

Posted 01 April 2008 - 01:27 PM

Here is the problem:

* Generate a RECURSIVE binary search.
* Be sure your Makefile will properly rebuild the run image.
* Inputs: a data file redirected with:
o the number of values in the array
o a sorted list of integers
o the number of values to search for
o a list of integers to search for.

Example output:
8 found at 2 during iteration 0.
21 found at 4 during iteration 1.
44 not found!

hints:
* Make sure that you wrote a RECURSIVE function for searching.
* Dynamically allocate and free memory as needed.
* You may want to use global variable to count iterations of your search (i.e. levels of your binary tree). Start counting from 0 (i.e. root of the the tree represents level 0).



As of right now I have the following issues:
* my compiler is telling me errors I don't understand
* my binary search method doesn't appear to work
* i have no idea how to use an input file to create an array and then search in it. I don't know if we're supposed to use fopen() or if when we run it we're just supposed to do: $ ./lab9 < datain.txt

Here's my code:

BinarySearch.c
/* Function designed to implement a recursive binary search */

int BinarySearch(int value, int first, int last, int array[]s, int *iteration)
{
	boolean found = false;
	int index;
	while(!found)
	{
		if (first<=last)
		{
			int mid = (first + last) / 2;
			if (value == array[mid])
			{
				found = true;
				return (mid);
			}
			else
			{
				*iteration =+ 1; 
				if (value < array[mid])
				{
					return (BinarySearch(value, first, mid-1));
				}
				
				else if (value > array[mid])
				{
					return (BinarySearch(value, mid+1, last));
				}
				
				else
				{
					found = true;
					return (-1);
				}
			}
		}
	}
}



lab9.c
/* Lindsey Hanna
 * lab6 section3
 * March 25, 2008
 * Pg. 549: design a program to implement a binary search
*/

#include <stdio.h>					// printf, scanf, fprint, fscanf, fopen, fclose definitions	
#include "Proto.h"					// prototypes of methods for calculation

int main(void)
{
	int value, first, last, iteration, index;
	int array[] = {1, 2, 5, 7, 9, 10, 45}; // just making an array to make sure my search method is actually working
	

	last = ((sizeof(array)) / (sizeof(int))) - 1;
	value = 2;
	first = 0;
	iteration = 0; 
	
	printf("\nvalue = %d, first = %d, last = %d, iteration = %d\n\n", value, first, last, iteration);

	index = BinarySearch(value, first, last, array, &iteration);
	
	if(index == -1)
	{
		printf("%4d not found!", value);
	}
	
	else
	{
		printf("%4d found at %4d during iteration %4d.", value, index, interation);
	}
	
	return(0);
}		



Makefile
note: all gcc changed to gc
# Makefile for lab9.c
# CS201
# makefile for multiple files
# lab9.o: lab9.c Proto.h

lab9: 	lab9.o BinarySearch.o
		gc -o lab9 lab9.o BinarySearch.o

lab9.o: lab9.c Proto.h
	gc -c lab9.c
	
BinarySearch.o: BinarySearch.c
	gc -c BinarySearch.c



Proto.h
/* proto.h - Function Prototypes */

#ifndef _PROTO_H
#define _PROTO_H
int BinarySearch(int value, int first, int last, int array[], int *iteration)
#endif




When I 'make' the file, here is what my compiler says:
note: all 'gcc' changed to gc

[lhanna@cslab26 lab9]$ make
make: Warning: File `lab9.c' has modification time 20 s in the future
gc -c lab9.c
lab9.c: In function ‘BinarySearch’:
lab9.c:11: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘{’ token
lab9.c:36: error: expected ‘{’ at end of input
make: *** [lab9.o] Error 1


Any help as to what's happening would be great.

-Kira

Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Binary Search

#2 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 02:55 PM

Two things I am noticing first off... in your Proto.h you appear to be missing a semicolon on the end of your function declaration. The second thing is that in BinarySearch c, where you define your parameters, you have an extra "s" on the end of int array[]s

So correct those two things and see what else pops up.
Was This Post Helpful? 0
  • +
  • -

#3 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 03:09 PM

okay i fixed some things (what you mentioned) and added some things. Here is my new code:

lab9.c
/* Lindsey Hanna
 * lab6 section3
 * March 25, 2008
 * Pg. 549: design a program to implement a binary search
*/

#include <stdio.h>					// printf, scanf, fprint, fscanf, fopen, fclose definitions	
#include "Proto.h"

int main(void)
{
	int value=0;								// variables for value to be searched
	int first=0;								// first and	
	int last=0;									// last indexes for searching
	int iteration=0;							// interation when value is found
	int index=0;								// found index
	int arraySize=0;							// size of array to be searched
	int i;										// loop counter
	int numberOfValues = 0;						// number of values to be searched

	int array[] = {1, 5, 8, 19, 21, 32}; // comment 2

	/*scanf("%d", &arraySize);					// scan number of elements to arraySize
	
	int array[arraySize];						// create array of set size
	for(i = 0; i < arraySize; i++)				// for all indexes... 
	{
		scanf("%d", array[i]);					// ...set array[index] to scanned number
	}
	
	scanf("%d", &numberOfValues);				// scan in number of values to search
	
	for(i = 1; i <= numberOfValues; i++)		// for all values...search array
	{*/
		last = (sizeof(array)) / (sizeof(int)) - 1;
		//scanf("%d", &value);
		
		value = 44;// comment 2
		first = 0;
		iteration = 0; 
		
		index = BinarySearch(value, first, last, array, &iteration);
	
		if(index == -1)
		{
			printf("%4d not found!\n", value);
		}
	
		else
		{
			printf("%4d found at %4d during iteration %4d.\n", value, index, iteration);
		}
	//}
	
	return(0);
}		



BinarySearch.c
/* Function designed to implement a recursive binary search */

int BinarySearch(int value, int first, int last, int array[], int *iteration)
{
	
	int index;
	if (value < array[first] || value > array[last])
	{
		return (-1);
	}
	else
	{
		if (first<=last)
		{
			int mid = (first + last) / 2;
			if (value == array[mid])
			{
				return (mid);
			}
			else
			{
				*iteration =+ 1; 
				if (value < array[mid])
				{
					return (BinarySearch(value, first, mid-1, array, iteration));
				}
				
				else
				{
					return (BinarySearch(value, mid+1, last, array, iteration));
				}
			}
		}
	}
}



Makefile is the same, Proto.h is the same except the error noted before, datain file is sample input file from previous post.


So. When I run how it is with that area commented out, it works fine. However, when I uncomment that part and comment off the parts marked // comment 2, I get a segmentation fault.

Since I'm obviously doing something wrong...what is the proper way to read in from a file? (Assuming when i run the program I do: $$ ./lab9 < datain)

-Kira
Was This Post Helpful? 0
  • +
  • -

#4 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 03:39 PM

We are moving in the right direction. Here are your next set of steps...

1) We need to dynamically allocate the memory for the array based on the size they entered, we can't just initialize the array with the value. Only constants can be used for this, but since you want to make it so the user can enter it, it has to be dynamic.

2) We then use "calloc" to initialize the array dimensions basing it on the number of items they entered and the size of the datatype used. If the user wants 6 slots of integers we are going to use 6 and sizeof(int).

3) Once we get the array setup, then we need to scanf into it. You forgot your ampersand here. You must send to the value to the address of the array subscript.

4) To top it off we are going to print just to show you that you are scanning in properly.

Don't forget to include <stdlib.h> in order to use calloc!

/* Lindsey Hanna
* lab6 section3
* March 25, 2008
* Pg. 549: design a program to implement a binary search
*/

#include <stdio.h>                    // printf, scanf, fprint, fscanf, fopen, fclose definitions    
#include <stdlib.h>					  // Needed for calloc
#include "Proto.h"

int main(void)
{
    int value=0;                                // variables for value to be searched
    int first=0;                                // first and    
    int last=0;                                    // last indexes for searching
    int iteration=0;                            // interation when value is found
    int index=0;                                // found index
    int arraySize=0;                            // size of array to be searched
    int i;                                        // loop counter
    int numberOfValues = 0;                        // number of values to be searched

	// Prompt for the array size
	printf("Enter a size for the array: ");
    scanf("%d", &arraySize);                    // scan number of elements to arraySize
    
	// Dynamically allocate the array based on the size the entered of type int.
	int* array = (int*) calloc(arraySize,sizeof(int));

	// Loop through this new array and scan in a value for each
	// Notice the use of the ampersand here to scan into the array

    for(i = 0; i < arraySize; i++)                // for all indexes...
    {
		printf("Scan in %d:", i);
        scanf("%d", &array[i]);                    // ...set array[index] to scanned number
    }
    
	// Lets run through the array just to show you the saved.
	printf("Now going to run through the array");

	for(int j=0; j < arraySize; j++) {
		printf("\nElement %d is: %d",j,array[j]);
	}
	
    scanf("%d", &numberOfValues);                // scan in number of values to search
    
    for(i = 1; i <= numberOfValues; i++)        // for all values...search array
    {
        last = (sizeof(array)) / (sizeof(int)) - 1;
        //scanf("%d", &value);
        
        value = 44;// comment 2
        first = 0;
        iteration = 0;
        
        index = BinarySearch(value, first, last, array, &iteration);
    
        if(index == -1)
        {
            printf("%4d not found!\n", value);
        }
    
        else
        {
            printf("%4d found at %4d during iteration %4d.\n", value, index, iteration);
        }
    }
    
    return(0);
} 



Take a look at the in-code comments to see what we are doing here. Then I am sure you will get the idea.

Next stop is your searching results! :)
Was This Post Helpful? 0
  • +
  • -

#5 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 03:48 PM

is there a way to allow 'user input' to just be a redirected file instead of a keyboard prompt?
Was This Post Helpful? 0
  • +
  • -

#6 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 03:54 PM

Sure, setup a file pointer and look into the function fscanf.

Example here...

fscanf - C Reference

:)
Was This Post Helpful? 0
  • +
  • -

#7 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:03 PM

I now have this:

/* Lindsey Hanna
 * lab6 section3
 * March 25, 2008
 * Pg. 549: design a program to implement a binary search
*/

#include <stdio.h>					// printf, scanf, fprint, fscanf, fopen, fclose definitions	
#include "Proto.h"

int main(void)
{
	int value=0;								// variables for value to be searched
	int first=0;								// first and	
	int last=0;									// last indexes for searching
	int iteration=0;							// interation when value is found
	int index=0;								// found index
	int arraySize=0;							// size of array to be searched
	int i;										// loop counter
	int numberOfValues = 0;						// number of values to be searched

	//int array[] = {1, 5, 8, 19, 21, 32};

	scanf("%d", &arraySize);					// scan number of elements to arraySize
	int * array = (int*) calloc(arraySize, sizeof(int));
	
	for(i = 0; i < arraySize; i++)				// for all indexes... 
	{
		scanf("%d", &array[i]);					// ...set array[index] to scanned number
	}
	
	scanf("%d", &numberOfValues);				// scan in number of values to search
	
	for(i = 1; i <= numberOfValues; i++)		// for all values...search array
	{
		last = (sizeof(array)) / (sizeof(int)) - 1;
		scanf("%d", &value);
		
		//value = 44;
		first = 0;
		iteration = 0; 
		
		index = BinarySearch(value, first, last, array, &iteration);
	
		if(index == -1)
		{
			printf("%4d not found!\n", value);
		}
	
		else
		{
			printf("%4d found at %4d during iteration %4d.\n", value, index, iteration);
		}
	}
	
	return(0);
}		



And i get the following when I run it:

[lhanna@cslab33 lab9]$ ./lab9 < datain
8 not found!
21 not found!
44 not found!
[lhanna@cslab33 lab9]$

which is obviously wrong.

Any idea what's going wrong?

-Kira
Was This Post Helpful? 0
  • +
  • -

#8 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:10 PM

You are going to make me rewrite this whole thing aren't you? hehe ;)
Was This Post Helpful? 0
  • +
  • -

#9 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:13 PM

View PostTreacherous M. Fresh, on 1 Apr, 2008 - 04:10 PM, said:

You are going to make me rewrite this whole thing aren't you? hehe ;)



Sorry! I fail pretty hard at C programming. *shakes head*

Your help is awesome though, so thank you. =)

-K
Was This Post Helpful? 0
  • +
  • -

#10 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:43 PM

Ok, here we go...

Now you don't really want the for loop. We are not searching for the number multiple times or searching multiple values of the array, the point of the array is to find the value in the array and return the index. Binary searches like this act on the whole array.

One other problem you were having is that you were attempting to calculate the size of the array. No need since we asked the user earlier for the size of the array. We can use that instead and subtract 1 to get the last index.

Once we have this, we can call the binary search and it will search the array for the value and return the index or -1.

/* Lindsey Hanna
* lab6 section3
* March 25, 2008
* Pg. 549: design a program to implement a binary search
*/

#include <stdio.h>                    // printf, scanf, fprint, fscanf, fopen, fclose definitions    
#include <stdlib.h>					  // Needed for calloc
#include "Proto.h"

int main(void)
{
    int value=0;                                // variables for value to be searched
    int first=0;                                // first and    
    int last=0;                                    // last indexes for searching
    int iteration=0;                            // interation when value is found
    int index=0;                                // found index
    int arraySize=0;                            // size of array to be searched
    int i;                                        // loop counter
    int numberOfValues = 0;                        // number of values to be searched

    // Prompt for the array size
    printf("Enter a size for the array: ");
    scanf("%d", &arraySize);                    // scan number of elements to arraySize
    
    // Dynamically allocate the array based on the size the entered of type int.
    int* array = (int*) calloc(arraySize,sizeof(int));

    // Loop through this new array and scan in a value for each
    // Notice the use of the ampersand here to scan into the array

    for(i = 0; i < arraySize; i++)                // for all indexes...
    {
        printf("Scan in %d:", i);
        scanf("%d", &array[i]);                    // ...set array[index] to scanned number
    }
    
    // Lets run through the array just to show you the saved.
    printf("Now going to run through the array");

    for(int j=0; j < arraySize; j++) {
        printf("\nElement %d is: %d",j,array[j]);
    }
	
    // No longer needed since we want to search whole array
    //scanf("%d", &numberOfValues); 
    
    // Instead of calculating size, we already know it is arraySize, index is arraySize -1
    last = arraySize - 1;
    
    // The value to hunt for, we could fscanf this if you want
    value = 44;
    first = 0;
    iteration = 0;
    
    // Call binarysearch once, no need for the loop
    index = BinarySearch(value, first, last, array, &iteration);

    if(index == -1)
    {
        printf("%4d not found!\n", value);
    }

    else
    {
        printf("%4d found at %4d during iteration %4d.\n", value, index, iteration);
    }

    
    return(0);
} 



See if this works for you. Read the in code comments to see further explanations. :)
Was This Post Helpful? 0
  • +
  • -

#11 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:52 PM

View PostTreacherous M. Fresh, on 1 Apr, 2008 - 04:43 PM, said:

// No longer needed since we want to search whole array
//scanf("%d", &numberOfValues);

See if this works for you. Read the in code comments to see further explanations. :)



The numberOfValues was how many items are being searched for, in this case there are three numbers being search for: 8, 21 and 44. This information was part of the data file. The for loop was so it did the binarysearch and printed the results for each value being seached for...

So I'm keeping that.

I fixed the part where I determine the size of the array and everything appears to be working now.

Although my prof mentioned something about 'freeing' memory...what is and how do I do that?

-Kira
Was This Post Helpful? 0
  • +
  • -

#12 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 04:59 PM

I removed it because you kept searching for 44 in the loop.

As for deleting check out the free() function for pointers. Example here....

free - C Reference

Glad things are working now for you.
Was This Post Helpful? 0
  • +
  • -

#13 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 05:00 PM

Actually I might be lying. I'm not sure if I'm getting the right output.

For the datain file:
20
1 5 8 19 21 32 50 63 70 74 78 81 85 89 94 100 102 108 111 120
5
1 20 32 89 120


I get:
[lhanna@cslab33 lab9]$ ./lab9 < datain
1 found at 0 during iteration 1.
20 not found!
32 found at 5 during iteration 1.
89 found at 13 during iteration 1.
120 found at 19 during iteration 1.

It doesn't seem like they should all be found at iteration 1...but maybe that's right? I'm not sure. =/

-Kira

PS - Thanks for helping with all my bothersome questions. =)
Was This Post Helpful? 0
  • +
  • -

#14 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4421
  • View blog
  • Posts: 12,289
  • Joined: 18-April 07

Re: Recursive Binary Search

Posted 01 April 2008 - 05:03 PM

I noticed in your BinarySearch method that you have *iteration =+ 1... try making it += and see if that helps with that.
Was This Post Helpful? 0
  • +
  • -

#15 kira89  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 61
  • Joined: 27-November 07

Re: Recursive Binary Search

Posted 01 April 2008 - 05:13 PM

View PostTreacherous M. Fresh, on 1 Apr, 2008 - 05:03 PM, said:

I noticed in your BinarySearch method that you have *iteration =+ 1... try making it += and see if that helps with that.


That appears to work. =)

Thanks for everything! You kick so many asses. ;)

-Kira
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1