searching
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace algos
{
class MainClass
{
public static void Main (string[] args)
{
int listSize = 100000000;
int findValue = 100000000 - 1; //let's look for the number 999
int[] nums = new int[listSize];
// populate list
for (int i = 0; i < listSize; i++)
nums [i] = i;
//running time of linear search
Stopwatch watch = new Stopwatch ();
watch.Start ();
var result = Algos.LinearSearch (findValue, nums);
Console.WriteLine (result);
watch.Stop ();
Console.WriteLine (watch.ElapsedMilliseconds);
// running time of binary search
watch.Restart ();
result = Algos.BinarySearch (findValue, nums, 0, nums.Length);
Console.WriteLine (result);
watch.Stop ();
Console.WriteLine (watch.ElapsedMilliseconds);
}
}
public static class Algos {
public static int LinearSearch (int x, int[] nums) {
foreach (var i in nums)
if (nums[i] == x)
return i;
return -1; // our error condition.
}
public static int BinarySearch (int x, int[] nums, int low, int high) {
int mid = (low + high) / 2; // get the midpoint
if (mid < 1) return -1; // element doesn’t exist in this case
if (x == nums[mid]) return x; //found element!
if (x > nums [mid]) return BinarySearch (x, nums, mid + 1, high); // the midpoint tells us which part of the list to traverse.
else return BinarySearch (x, nums, low, mid - 1); // the midpoint tells us which part of the list to traverse.
}
}
}