# Recursive Binary Search

Page 1 of 1

## 14 Replies - 34503 Views - Last Post: 01 April 2008 - 05:13 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=47888&amp;s=eede10e6d9534903c42a9b6840d5009d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 kira89

Reputation: 2
• 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.

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)
{
}

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

[[email protected] 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

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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.

### #3 kira89

Reputation: 2
• 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)
{
}

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

### #4 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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)
{
}

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!

### #5 kira89

Reputation: 2
• 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?

### #6 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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

### #7 kira89

Reputation: 2
• 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)
{
}

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

return(0);
}

```

And i get the following when I run it:

[[email protected] lab9]\$ ./lab9 < datain
[[email protected] lab9]\$

which is obviously wrong.

Any idea what's going wrong?

-Kira

### #8 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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

### #9 kira89

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

## Re: Recursive Binary Search

Posted 01 April 2008 - 04:13 PM

Treacherous 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

### #10 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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)
{
}

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.

### #11 kira89

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

## Re: Recursive Binary Search

Posted 01 April 2008 - 04:52 PM

Treacherous 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

### #12 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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.

### #13 kira89

Reputation: 2
• 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:
[[email protected] lab9]\$ ./lab9 < datain
1 found at 0 during iteration 1.
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. =)

### #14 Martyr2

• Programming Theoretician

Reputation: 5207
• Posts: 13,953
• 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.

### #15 kira89

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

## Re: Recursive Binary Search

Posted 01 April 2008 - 05:13 PM

Treacherous 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