944,164 Members | Top Members by Rank

Software Development > C++ > binary search
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 2959
  • C++ RSS
Permalink
Nov 9th, 2004
-1

binary search

Expand Post »
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


C++ Syntax (Toggle Plain Text)
  1. #include <iostream> 
  2. #include <ctime> 
  3.  
  4.  
  5. usingnamespace std; 
  6.  
  7. int bin_search(int a[], int n, int& target); 
  8.  
  9.  
  10.  
  11. // sel sort
  12.  
  13. void selsort(int a[], int size)
  14.  
  15. {
  16.  
  17. int i, j, maxpos, temp;
  18.  
  19. for (i=0; i < size; i++)
  20.  
  21. {
  22.  
  23. maxpos = i;
  24.  
  25. for (j=maxpos+1; j < size; j++)
  26.  
  27. if (a[j] > a[maxpos])maxpos = j;
  28.  
  29. temp = a[i];
  30.  
  31. a[i] = a[maxpos];
  32.  
  33. a[maxpos] = temp;
  34.  
  35. }
  36.  
  37.  
  38.  
  39. }
  40.  
  41. int main() 
  42.  
  43. { 
  44.  
  45.  
  46.  
  47. int A[150];
  48.  
  49. int target;
  50.  
  51. int num_searches = 0;
  52.  
  53. int suc_search = 0;
  54.  
  55. int tests = 0;
  56.  
  57. srand((unsigned)time(NULL));
  58.  
  59. int random_integer; 
  60.  
  61.  
  62.  
  63. // random nums
  64.  
  65. { 
  66.  
  67. for (int i = 0; i < 150; i++)
  68.  
  69. A[i] = (rand()%200)+1;
  70.  
  71. // sorts
  72.  
  73. selsort(A,150);
  74.  
  75. for (int i = 0; i < 200; i++)
  76.  
  77.  
  78.  
  79. {
  80.  
  81. target = (rand()%200)+1;
  82.  
  83. num_searches++;
  84.  
  85. if (bin_search(A, 150, target)!=-1)
  86.  
  87. suc_search++; // sucessfull searches
  88.  
  89. }
  90.  
  91. int bin_search (int a[], int n, int& target)
  92.  
  93. {
  94.  
  95. // Precondition: array a is sorted in ascending order 
  96.  
  97. int first = 0;
  98.  
  99. int last = n - 1;
  100.  
  101. int mid = (first + last) / 2;
  102.  
  103. while ((a[mid] != target) && (first <= last)) 
  104.  
  105. { 
  106.  
  107. tests++;
  108.  
  109. if (target < a[mid])
  110.  
  111. last = mid - 1;
  112.  
  113. else
  114.  
  115. first = mid + 1;
  116.  
  117. mid = (first + last) / 2;
  118.  
  119. }
  120.  
  121. if (a[mid] == target) return mid;
  122.  
  123. return -1; // target not found
  124.  
  125. }
  126.  
  127. int report (double num_searches, double suc_search, double tests);
  128.  
  129. {
  130.  
  131. cout <<"there are ["<< num_searches<<"] num of searches" << endl;
  132.  
  133. cout <<"there are ["<< suc_search<<"] num of sucessfull searches" << endl;
  134.  
  135. cout <<"there are ["<< suc_search/num_searches<<"] num of average searches" << endl;
  136.  
  137. cout <<"there are ["<< tests/200<<"] percent of sucessfull searches" << endl;
  138.  
  139. system("pause");
  140.  
  141. cout << "Press Enter to exit." << endl;
  142.  
  143.  
  144.  
  145. }
  146.  
  147. }
  148.  
  149. }
Last edited by alc6379; Nov 9th, 2004 at 7:42 pm. Reason: added [code] tags
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
kerrigan88 is offline Offline
3 posts
since Nov 2004
Permalink
Nov 9th, 2004
0

Re: binary search

>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.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Permalink
Nov 9th, 2004
0

Re: binary search

Quote 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?
Reputation Points: 10
Solved Threads: 0
Newbie Poster
kerrigan88 is offline Offline
3 posts
since Nov 2004
Permalink
Nov 9th, 2004
0

Re: binary search

Quote 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?

 
#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;
	
}
}
}
Reputation Points: 10
Solved Threads: 0
Newbie Poster
kerrigan88 is offline Offline
3 posts
since Nov 2004
Permalink
Nov 9th, 2004
0

Re: binary search

n is the size of the array, it's not terribly difficult to figure out how to get it into bin_search. hint: pass it as an argument.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: I need help
Next Thread in C++ Forum Timeline: How do I make my do while and counting of my words run





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC