Sereche

 Profile Answers by Sereche 

• Jul 9th, 2012

 

This seems to be a question about time complexity / big-O notation. Time complexity basically tells you how the program running time scales, as a function of one of the variables of input (in most cases, the size of the input). Your first function (the binary search) runs in O(log n) time, the second runs in O(n) time. What this means is best illustrated with an example:

Lets say that running your binary search function on an array of 1,000 elements takes, on average, 1 second. You would then expect the function to take about 2 seconds to run on an array of 1,000,000 elements, and about 3 seconds on an array of 1 billion elements. Similarly, with an O(n)-time algorithm, you would expect the running time to roughly double when you double the size of the input set.

Note that these estimates are just that, estimates. At low values of n, the information is almost meaningless, as overhead costs become a larger factor. In addition, not all O(n) algorithms will run in the same amount of time, though, for large enough n, those times should differ by a constant factor (i.e. one O(n) algorithm takes roughly twice as long as a different O(n) algorithm).

For more information on time complexity, I would recommend reading http://en.wikipedia.org/wiki/Time_complexity.


Also, note that the code youve provided is not valid C (or, for that matter, any language that I can recognize). The public/static qualifiers are meaningless in C (C#, maybe?). Passing an array as a parameter is not done correctly (and is typically not done at all in C or C++; again, did you mean C#?). Since youve tagged this question as C++, and put C in the title, Ive included code which should be valid in both C/C++. (Note: I havent actually tested it, so there is always the possibility of some small error)

Code
int intBinarySearch(int x, int* a, int length) {


   int low = 0;


   int high = length - 1;


   int mid;


 


   while (low <= high) {


      mid = (low + high) / 2


      if(a[mid] < x)


         low = mid + 1;


      else if (a[mid] > x)


         high = mid - 1;


      else


         return mid;


   }


   return -1;


}


 


 


int findMeanOfInput() {


   int n = 0;


   int sum = 0;


   int x;


   


   //Note that the following three lines can be replaced with


   // cin >> x;


   //if you are writing in C++ 


   char buf[1024]; 


   gets(buf);          


   x = atoi(buf);


 


   while(x != 99)


   {


      ++n;


      sum += x;


 


      //Again, these three lines can be replace with cin in C++


      char buf[1024]; 


      gets(buf);          


      x = atoi(buf);


   }


   return sum / n;


}