DaniWeb Forum Index > Software Development > C++

C++ RSS

binary search

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2004

Posts: 3

Reputation: kerrigan88 is an unknown quantity at this point

Solved Threads: 0

kerrigan88 kerrigan88 is offline

Offline

Newbie Poster

binary search

-1

Nov 9th, 2004

Alright, mine's a long one. The error I keep on getting is bin_search local funtion defs are illegal.
Think there is something worng with my binary search. Anyone see what's worng with it?
I'm sapose to have it display
1. The number of searches completed
2. The number of successful searches
3. The percentage of successful searches
4. The average number of tests per search

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream> 
#include <ctime> 
 
usingnamespace std; 
 
int bin_search(int a[], int n, int& target); 
 
// sel sort
 
void selsort(int a[], int size)
 
{
 
int i, j, maxpos, temp;
 
for (i=0; i < size; i++)
 
{
 
maxpos = i;
 
for (j=maxpos+1; j < size; j++)
 
if (a[j] > a[maxpos])maxpos = j;
 
temp = a[i];
 
a[i] = a[maxpos];
 
a[maxpos] = temp;
 
}
 
}
 
int main() 
 
{ 
 
int A[150];
 
int target;
 
int num_searches = 0;
 
int suc_search = 0;
 
int tests = 0;
 
srand((unsigned)time(NULL));
 
int random_integer; 
 
// random nums
 
{ 
 
for (int i = 0; i < 150; i++)
 
A[i] = (rand()%200)+1;
 
// sorts
 
selsort(A,150);
 
for (int i = 0; i < 200; i++)
 
{
 
target = (rand()%200)+1;
 
num_searches++;
 
if (bin_search(A, 150, target)!=-1)
 
suc_search++; // sucessfull searches
 
}
 
int bin_search (int a[], int n, int& target)
 
{
 
// Precondition: array a is sorted in ascending order 
 
int first = 0;
 
int last = n - 1;
 
int mid = (first + last) / 2;
 
while ((a[mid] != target) && (first <= last)) 
 
{ 
 
tests++;
 
if (target < a[mid])
 
last = mid - 1;
 
else
 
first = mid + 1;
 
mid = (first + last) / 2;
 
}
 
if (a[mid] == target) return mid;
 
return -1; // target not found
 
}
 
int report (double num_searches, double suc_search, double tests);
 
{
 
cout <<"there are ["<< num_searches<<"] num of searches" << endl;
 
cout <<"there are ["<< suc_search<<"] num of sucessfull searches" << endl;
 
cout <<"there are ["<< suc_search/num_searches<<"] num of average searches" << endl;
 
cout <<"there are ["<< tests/200<<"] percent of sucessfull searches" << endl;
 
system("pause");
 
cout << "Press Enter to exit." << endl;
 
}
 
}
 
}
#include <iostream> 
#include <ctime> 

usingnamespace std; 

int bin_search(int a[], int n, int& target); 

// sel sort

void selsort(int a[], int size)

{

int i, j, maxpos, temp;

for (i=0; i < size; i++)

{

maxpos = i;

for (j=maxpos+1; j < size; j++)

if (a[j] > a[maxpos])maxpos = j;

temp = a[i];

a[i] = a[maxpos];

a[maxpos] = temp;

}

}

int main() 

{ 

int A[150];

int target;

int num_searches = 0;

int suc_search = 0;

int tests = 0;

srand((unsigned)time(NULL));

int random_integer; 

// random nums

{ 

for (int i = 0; i < 150; i++)

A[i] = (rand()%200)+1;

// sorts

selsort(A,150);

for (int i = 0; i < 200; i++)

{

target = (rand()%200)+1;

num_searches++;

if (bin_search(A, 150, target)!=-1)

suc_search++; // sucessfull searches

}

int bin_search (int a[], int n, int& target)

{

// Precondition: array a is sorted in ascending order 

int first = 0;

int last = n - 1;

int mid = (first + last) / 2;

while ((a[mid] != target) && (first <= last)) 

{ 

tests++;

if (target < a[mid])

last = mid - 1;

else

first = mid + 1;

mid = (first + last) / 2;

}

if (a[mid] == target) return mid;

return -1; // target not found

}

int report (double num_searches, double suc_search, double tests);

{

cout <<"there are ["<< num_searches<<"] num of searches" << endl;

cout <<"there are ["<< suc_search<<"] num of sucessfull searches" << endl;

cout <<"there are ["<< suc_search/num_searches<<"] num of average searches" << endl;

cout <<"there are ["<< tests/200<<"] percent of sucessfull searches" << endl;

system("pause");

cout << "Press Enter to exit." << endl;

}

}

}

Last edited by alc6379; Nov 9th, 2004 at 7:42 pm. Reason: added [code] tags

•

Join Date: Sep 2004

Posts: 7,630

Reputation: Narue has a reputation beyond repute

Solved Threads: 718

Narue

Offline

Code Goddess

Re: binary search

Nov 9th, 2004

>The error I keep on getting is bin_search local funtion defs are illegal.
You should listen to that error. It's telling you that you can't have a function definition nested inside of another function definition. bin_search is defined inside main, so that's illegal. What about report, you say? It's inside of main too, but because you terminated it with a semicolon, that makes it a declaration, which is perfectly legal. For proper operation you may want to fix that as well.

I'm here to prove you wrong.

•

Join Date: Nov 2004

Posts: 3

Reputation: kerrigan88 is an unknown quantity at this point

Solved Threads: 0

kerrigan88 kerrigan88 is offline

Offline

Newbie Poster

Re: binary search

Nov 9th, 2004

•

Originally Posted by Narue

>The error I keep on getting is bin_search local funtion defs are illegal.
You should listen to that error. It's telling you that you can't have a function definition nested inside of another function definition. bin_search is defined inside main, so that's illegal. What about report, you say? It's inside of main too, but because you terminated it with a semicolon, that makes it a declaration, which is perfectly legal. For proper operation you may want to fix that as well.

Then should I move it outside the main or where to? Thes reprot would be wong too?

•

Join Date: Nov 2004

Posts: 3

Reputation: kerrigan88 is an unknown quantity at this point

Solved Threads: 0

kerrigan88 kerrigan88 is offline

Offline

Newbie Poster

Re: binary search

Nov 9th, 2004

•

Originally Posted by kerrigan88

Then should I move it outside the main or where to? Thes reprot would be wong too?

Ok, I moved the bin_search out, now I get the error "n undeclared identifier." But whe I try to declare it, I jsut get more error. So where do I declare it?

Help with Code Tags

(Toggle Plain Text)

 
#include <iostream> 
#include <ctime> 


using namespace std; 




	 int  bin_search(int a[], int tests, int& target); 


	 // sel sort
	 void  selsort(int a[], int size)

{
        int i, j, maxpos, temp;
        for (i=0; i < size; i++)
        {
                maxpos = i;
                for (j=maxpos+1; j < size; j++)
                        if (a[j] > a[maxpos])maxpos = j;
                temp = a[i];
                a[i] = a[maxpos];
                a[maxpos] = temp;
        }
        
}



// bin search

int bin_search (int  a[], inttests,  int& target)
{
 // Precondition: array a is sorted in ascending order  

  int  first = 0;
  int  last = n - 1;
  int mid = (first + last) / 2;

  while ((a[mid] != target) && (first <= last)) 
  { 
	  tests++;
    if  (target < a[mid])
      last = mid - 1;
    else
      first = mid + 1;
    mid = (first + last) / 2;
  }
if (a[mid] == target) return  mid;
return -1;  // target not found

}

int  main() 
{ 

	int A[150];
	int  target;
	int  num_searches = 0;
	int suc_search = 0;
	int tests = 0;


srand((unsigned)time(NULL));
int random_integer; 


// random nums
{ 
	for (int i = 0; i < 150; i++)
		A[i] = (rand()%200)+1;

// sorts

	selsort(A,150);
	for int i = 0; i < 200; i++)
	
	{
		target = (rand()%200)+1;
		 num_searches++;
			 if  (bin_search(A, 150, target)!=-1)
			suc_search++;   // sucessfull searches	}



int  report (double  num_searches, double suc_search, double  tests);

{

cout <<"there are ["<< num_searches<<"] num of searches"  << endl;
cout <<"there are ["<< suc_search<<"] num of succfull searches"  << endl;
cout <<"there are ["<< suc_search/num_searches<<"] num of average searches"  << endl;
cout <<"there are ["<< tests/200<<"] percent of succfull searches"  << endl;

	  system("pause");

	cout << "Press Enter to exit." << endl;
	
}
}
}