searching

SearchAlgos.cs

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.
		}
	}
}