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));

}

}

}