A binary search is an algorithm is able to find a specific value within a sorted array by making increasingly acurate guesses based on a comparision result. I was discussing this with a friend at work the other day and thought I would put one together in C# for illustrative purposes.
First we need to create the array with random data and then sort this array. I decided that using guids would provide a good level of random data for our test. I therefore create a million guids in my array then sort it. This is shown below.
///
/// Mains the specified args.
///
static void Main(string[] args)
{
//Setup random data.
List<String> RandomItems = new List<string>();
for (int i = 0; i < 1000000; i++){RandomItems.Add(Guid.NewGuid().ToString());}
//Get search item and sort.
string searchFor = RandomItems[345];
RandomItems.Sort();
Console.WriteLine("Press enter to run test");
Console.ReadLine();
}
Next I created the algorithm which would quickly narrow down on the value we are searching for. There are 3 things to remember when it comes to binary searches.
- Find the median of a particular range within your array.
- Compare the value at that midpoint to see if ths greaterthan, lessthan or Equal.
- Call the same method recursively in order to narrow the search.
The Binary search class is shown below.
///
/// Finds the index. (Public Overload.)
///
///
///The index of the specified item.
public static int FindIndex(List<String> sortedList,string searchCriteria)
{
return FindIndex(sortedList, searchCriteria, 0,sortedList.Count);
}
///
/// Finds the index.
///
///The index of the specified
private static int FindIndex(List<string> sortedList,string searchCriteria, int startPosition, int endPosition)
{
int lastPos = startPosition;
int range = (endPosition - startPosition);
if (range == 0) return 0;
int midPoint = (range / 2) + startPosition;
int equality = sortedList[midPoint].CompareTo(searchCriteria);
Console.WriteLine(midPoint);
//Equals
if (equality == 0)
return midPoint;
//Greater than
if (equality == -1)
return FindIndex(sortedList, searchCriteria, midPoint, endPosition);
//Less than
if (equality == 1)
return FindIndex(sortedList, searchCriteria, lastPos, midPoint);
return -1;
}
Finally, I want to run the algorithm and work out the cost of finding my value within a million strings. So we need to add the following to our static main.
//Run our binary search.
DateTime start = DateTime.Now;
Console.WriteLine("Item found at position [" + BinarySearch.FindIndex(RandomItems, searchFor).ToString() + "]");
DateTime end = DateTime.Now;
Console.WriteLine("Cost M/s: " + new TimeSpan(end.Ticks - start.Ticks).TotalMilliseconds.ToString());
Console.ReadLine();
The results of running this algorithm are shown here.
Press enter to run test
500000
250000
375000
312500
343750
328125
335937
332031
330078
329101
329589
329833
329955
330016
329985
330000
330008
330012
330014
330013
Item found at position [330013]
Cost M/s: 5