Question

Problem:

The code I have below compiled/debugged using C#, however I need to measure the time it takes to do the 10,000,000 searches for each of the eight arrays. Could you compare the timings to the theoretical timings the algorithm binary search provides.

Instructions prior to this:

Implement a binary search function in C#. In this program we are to carry out the same 10,000,000 unsuccessful searches for eight different-sized arays, namely arrays of sizes 128, 512, 2,048, 8,192, 32,768, 131,072, 524,288, and 2,097,152.

Code:

using System;

using System.Diagnostics;

class MainClass

{

static int search(int[] arr, int l, int r, int x)

{

if (r >= 1)

{

int mid = 1 + (r - 1) / 2;

if (arr[mid] == x)

return mid;

if (arr[mid] > x)

return search(arr, 1, mid - 1, x);

return search(arr, mid + 1, r, x);

}

return -1;

}

public static void Main (string[] args) {

{

int size = 2097152;

int[] arr = new int[size];

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

{

arr[i] = 0;

}

int x = 1;

int result = 0;

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

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

{

result = search(arr, 0, size - 1, x);

}

stopwatch.Stop();

TimeSpan stopwatchElapsed = stopwatch.Elapsed;

Console.WriteLine(Convert.ToInt32(stopwatchElapsed.TotalMilliseconds));

}

}

}

Answer 1

Theoretical time depends upon number of operations cpu can handle.

Assuming CPU frequency = 1Ghz = 10^9

Binary search require O(logn) operations

Total searches = 10,000,000

total time = 10,000,000*logn in nanoseconds = 10*logn milliseconds

n=128

logn = 7

time = 70ms

n=512

logn = 9

time = 90ms

n=2,048

logn = 11

time = 110ms

n=8,192

logn = 13

time = 130ms

n=32,768

logn = 15

time = 150ms

n=131,072

logn = 17

time = 170ms

n=524,288

logn = 19

time = 190ms

n=2,097,152

logn = 21

time = 210ms

Program (Similar to yours)

using System;
using System.Diagnostics;
class Program{

static int search(int[] arr, int l, int r, int x){
if (r >= l){
int mid = (l+r) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return search(arr, l, mid - 1, x);
return search(arr, mid + 1, r, x);
}
return -1;
}
public static void Main (string[] args) {
int size = 2097152;
int[] arr = new int[size];
for (int i = 0; i < size; i++)
arr[i] = 0;
int x = 1;
int result = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 10000000; i++)
result = search(arr, 0, size - 1, x);
stopwatch.Stop();
TimeSpan stopwatchElapsed = stopwatch.Elapsed;
Console.WriteLine("Time:");
Console.WriteLine(Convert.ToInt32(stopwatchElapsed.TotalMilliseconds));
}
}