By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,687 Members | 1,989 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,687 IT Pros & Developers. It's quick & easy.

average time on a sequential search

P: 3
So, I'm about to do a sequential search on a table (n contents) of random numbers.
I have to print
  • the average between the number of comparisons and the contents of the table (n)
  • and the average time
for each sequential search.

I wrote:



Expand|Select|Wrap|Line Numbers
  1. sum = 0;
  2.      for (i=1; i<=10; i++)
  3.     {
  4.  
  5.          x = rand() % LIMIT + 1;
  6.          printf ("A number between 1 and 30000 : %d\n", x);
  7.  
  8.          start = clock();
  9.  
  10.          sum2 = 0;
  11.          done = 0;
  12.          j=1;
  13.          do
  14.          {
  15.  
  16.              if (a[j]==x)
  17.              {
  18.                   done = 1;
  19.              }
  20.              j++;
  21.              sum2 = sum2 + 1;
  22.          }
  23.          while ((j<=n) && (done == 0));
  24.  
  25.          average= sum2 / n;
  26.          printf("he average of comparison between the contents of the table for the %d search is: %.2f\n", i, average);
  27.  
  28.          end = clock();
  29.          elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
  30.          sum = sum + elapsed;
  31. avetime= sum / 10;
  32.     printf("the average time for each sequential search %.2f\n", avetime);


BUT I get 1 for every average and zero for the average time. Why?
Oct 18 '08 #1
Share this Question
Share on Google+
5 Replies


Ganon11
Expert 2.5K+
P: 3,652
What types are sum2 and m? If they are both ints, you probably won't get accurate results.
Oct 18 '08 #2

P: 3
What types are sum2 and m? If they are both ints, you probably won't get accurate results.
I have
int i, j, x, sum2;
int n, done;
float average;
clock_t start, end;
double elapsed, sum, avetime;

should i change it? into what?
Oct 18 '08 #3

Ganon11
Expert 2.5K+
P: 3,652
Well, an int divided by an int is an int...no matter what. So if you have 24/51, it evaluates to 0. If you have 50/51, it evaluates to 0. If you have 199/100, it evaluates to 1. I have a feeling this is what is happening.

Try changing n or sum2 (or both) to a double. A double divided by a double (or an int divided by a double, or a double divided by an int) is a double.
Oct 18 '08 #4

P: 3
Well, an int divided by an int is an int...no matter what. So if you have 24/51, it evaluates to 0. If you have 50/51, it evaluates to 0. If you have 199/100, it evaluates to 1. I have a feeling this is what is happening.

Try changing n or sum2 (or both) to a double. A double divided by a double (or an int divided by a double, or a double divided by an int) is a double.
thanks. i think it worked out!!
Oct 19 '08 #5

Expert 10K+
P: 11,448
If you have correctly implemtented your little simulation you should've found out
that in order to find an item in a random sequence of n items you'd have to search
n/2 items on average.

Corollary: a rotating hard disk needs half a revolution on average to position the
correct wanted sector under the read/write head of the disk; therefore I propose
a revolutionary speedup: mount those read/write heads 180 degrees opposite
from where they are now to establish a zero rotation seach time. qed.

kind regards,

Jos (<--- genius ;-)
Oct 19 '08 #6

Post your reply

Sign in to post your reply or Sign up for a free account.