# Binary search in C#

: An implementation of the classic Binary Search in C#

# Introduction

Binary search is the classic search algorithm, and I remember implementing it in C at University. As an experiment I’m going to implement it in C# to see if the line of business applications I usually build have rotted my brain.

# Algorithm

As Wikipedia explains, Binary Search follows this procedure:

Given an array A of n elements with values or records A0, A1, …, An−1, sorted such that A0 ≤ A1 ≤ … ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.

1. Set L to 0 and R to n − 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
4. If Am < T, set L to m + 1 and go to step 2.
5. If Am > T, set R to m − 1 and go to step 2.
6. Now Am = T, the search is done; return m.

This is actually Knuth’s algorithm, from The Art of Computer Programming as stated in the footnote on the Wikipedia article.

# Implementation

It’s worth noting that this is merely a fun exercise, and that .net has an implementation in Array.BinarySearch which is much better than the implementation below and I would always use that instead.

It’s also worth mentioning that I’m cheating a little bit and assuming that the array is already sorted, and that it only works on `int`’s.

## Console runner

Here is the console runner:

Here is the output:

Written by Stuart on