424,687 Members | 1,989 Online
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 sum = 0;      for (i=1; i<=10; i++)     {            x = rand() % LIMIT + 1;          printf ("A number between 1 and 30000 : %d\n", x);            start = clock();            sum2 = 0;          done = 0;          j=1;          do          {                if (a[j]==x)              {                   done = 1;              }              j++;              sum2 = sum2 + 1;          }          while ((j<=n) && (done == 0));            average= sum2 / n;          printf("he average of comparison between the contents of the table for the %d search is: %.2f\n", i, average);            end = clock();          elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;          sum = sum + elapsed; avetime= sum / 10;     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
5 Replies

 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

 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