First example. We use Array.BinarySearch. This method has one version that accepts a type parameter, which we can specify in angle brackets. The C# compiler will infer this type.
Part 1 We allocate an array containing 6 string literals. The array variable is a reference to this data in memory.
Part 2 We call Array.BinarySearch. In this example the type is inferred on all 3 calls.
Part 3 We print the results from the Array.BinarySearch method calls. The correct indexes were found.
using System;
// Part 1: source array that is ordered ascending.
string[] array = { "a", "e", "m", "n", "x", "z" };
// Part 2: call versions of the BinarySearch method.
int index1 = Array.BinarySearch(array, "m");
int index2 = Array.BinarySearch<string>(array, "x");
int index3 = Array.BinarySearch<string>(array, "E", StringComparer.OrdinalIgnoreCase);
// Part 3: write results.
Console.WriteLine(index1);
Console.WriteLine(index2);
Console.WriteLine(index3);2
4
1
Benchmark. This next program benchmarks Array.BinarySearch against Array.FindIndex. It generates a string array of 10000 random file names and sorts them.
Result The Array.BinarySearch method was over 40 times faster than Array.FindIndex.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
class Program
{
static string[] GetArray()
{
List<string> list = new List<string>();
for (int i = 0; i < 10000; i++)
{
list.Add(Path.GetRandomFileName());
}
string[] array = list.ToArray();
Array.Sort(array);
return array;
}
const int _max = 10000;
static void Main()
{
string[] array = GetArray();
var s1 = Stopwatch.StartNew();
// Version 1: use BinarySearch.
for (int i = 0; i < _max; i++)
{
int index1 = i % 10000;
string key = array[index1];
int index2 = Array.BinarySearch<string>(array, key);
if (index1 != index2)
{
throw new Exception();
}
}
s1.Stop();
var s2 = Stopwatch.StartNew();
// Version 2: use FindIndex.
for (int i = 0; i < _max; i++)
{
int index1 = i % 10000;
string key = array[index1];
int index2 = Array.FindIndex(array, element => element == key);
if (index1 != index2)
{
throw new Exception();
}
}
s2.Stop();
Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
}
} 1336.09 ns BinarySearch
57243.46 ns FindIndex
Discussion. The binary search algorithm in computer science has much better performance than a linear search in most nontrivial cases.
However My testing shows that its performance is far worse than a Dictionary or hash table on string keys.
Tip Sometimes when memory usage is important, binary search can help improve that metric.
Summary. The C# compiler infers type parameters on Array.BinarySearch. We can compare elements based on a StringComparer class. Finally, we noted the performance of this method.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Sep 4, 2024 (rewrite).