Skip to content

Instantly share code, notes, and snippets.

@alexander-williamson
Created July 11, 2019 22:27
Show Gist options
  • Save alexander-williamson/ac444a54aa67b979a3fa83e22238a2e8 to your computer and use it in GitHub Desktop.
Save alexander-williamson/ac444a54aa67b979a3fa83e22238a2e8 to your computer and use it in GitHub Desktop.
BinarySearch in C#
using System;
using System.Linq;
using NUnit.Framework;
namespace Alexw.Katas.BinarySearch
{
public class BinarySearchTests
{
private static readonly DataItem[] Items =
{
new DataItem(1, true),
new DataItem(2, true),
new DataItem(3, true),
new DataItem(4, true),
new DataItem(5, true),
new DataItem(6, true),
new DataItem(7, true),
new DataItem(8, true),
new DataItem(9, true),
new DataItem(10, true),
new DataItem(11, true),
new DataItem(12, true),
new DataItem(13, false)
};
[Test]
public void GivenListOfItems_FindTheFirstElementBroken()
{
var result = new BinarySearcher().Find(Items);
Assert.That(result, Is.EqualTo(11));
}
}
public class BinarySearcher
{
private const bool SearchingFor = true;
public int Find(DataItem[] input)
{
var min = 1;
var max = input.Length;
var current = max / 2;
while (true)
{
var itemBelow = input.ElementAtOrDefault(current - 1);
var item = input.ElementAt(current);
var itemAbove = input.ElementAtOrDefault(current + 1);
var result = IsMatch(itemBelow, item, itemAbove);
if (result > 0)
{
// we think it's above us
min = current + 1;
}
else if (result < 0)
{
// we think it's below us
max = current - 1;
}
else
{
// this is the item
return current;
}
current = (min + max) / 2;
}
}
public int IsMatch(DataItem itemBelow, DataItem item, DataItem itemAbove)
{
if (itemAbove != null && itemAbove.Value == SearchingFor)
return 1;
if (item.Value)
return 0;
return -1;
}
}
public class DataItem
{
public int Key { get; }
public bool Value { get; }
public DataItem(int key, bool value)
{
Key = key;
Value = value;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment