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.
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.
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
Here is the console runner:
Here is the output: