Join 136,008 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,333 people online right now. Registration is fast and FREE... Join Now!
* 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
CODE
/* 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)); }
/* 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
CODE
# Makefile for lab9.c # CS201 # makefile for multiple files # lab9.o: lab9.c Proto.h
#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
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.
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
CODE
/* 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)); }
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)
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!
cpp
/* Lindsey Hanna * lab6 section3 * March 25, 2008 * Pg. 549: design a program to implement a binary search */
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");
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]$
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.
cpp
/* Lindsey Hanna * lab6 section3 * March 25, 2008 * Pg. 549: design a program to implement a binary search */
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");
QUOTE(Treacherous M. Fresh @ 1 Apr, 2008 - 04:43 PM)
// 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?
|