# 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.

- Set L to 0 and R to n − 1.
- If L > R, the search terminates as unsuccessful.
- Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
- If Am < T, set L to m + 1 and go to step 2.
- If Am > T, set R to m − 1 and go to step 2.
- 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.

## My implementation

## Console runner

Here is the console runner:

Here is the output:

## Comments