Skip to content

Instantly share code, notes, and snippets.

@regularcoder
Last active December 17, 2015 18:19
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save regularcoder/5652650 to your computer and use it in GitHub Desktop.
Save regularcoder/5652650 to your computer and use it in GitHub Desktop.
Binary search in C#
/*
* Created by SharpDevelop.
* Date: 5/26/2013
* Time: 4:04 PM
*
*
*/
using System;
using System.Collections.Generic;
namespace Utility
{
/// <summary>
/// Helper methods related to input/output
/// </summary>
public class IOHelper
{
public IOHelper()
{
}
/// <summary>
/// Converts a sting into a lidy of integers (
/// assumes that are separated by spaces)
/// </summary>
public static List<Int32> ConvertStringToIntList(string input)
{
List<Int32> intList = new List<Int32>();
String[] inputNums = input.Split(' ');
foreach (string singleNum in inputNums)
{
intList.Add(Convert.ToInt32(singleNum));
}
return intList;
}
}
}
/*
* Created by SharpDevelop.
* Date: 5/26/2013
* Time: 3:54 PM
*
*
*/
using System;
using System.Collections.Generic;
using Utility;
namespace SortingDemo
{
class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Enter source list: ");
List<int> source = IOHelper.ConvertStringToIntList(Console.ReadLine());
Console.WriteLine("Enter number to search for: ");
int item = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Output of binary search: {0}", source.BinSearch(item));
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
}
}
/*
* Created by SharpDevelop.
* Date: 5/26/2013
* Time: 3:39 PM
*
*
*/
using System;
using System.Collections.Generic;
namespace Utility
{
/// <summary>
/// Extension methods related to searching
/// </summary>
public static class SearchExtensions
{
/// <summary>
/// Searches through a list using binary search algorithm
/// </summary>
/// <param name="source"></param>
/// <param name="searchKey"></param>
/// <returns></returns>
public static int BinSearch<T>(this List<T> source, T searchKey)
where T:IComparable
{
int low = 0;
int high = source.Count - 1;
int mid;
do
{
mid = low + ((high - low) / 2);
int compareResult = searchKey.CompareTo(source[mid]);
//If item is at current mid position we can stop
if(compareResult == 0)
{
return mid;
}
//Otherwise look at either lower half or upper half of the list
else
{
//If searchKey < source[mid] then we need to look at
//left half of the list
if(compareResult < 0)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
} while (low < high);
return -1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment