Last active
December 17, 2015 18:19
-
-
Save regularcoder/5652650 to your computer and use it in GitHub Desktop.
Binary search in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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