I was writing code this week and needed to search an array of integers for a target value. In this case the values in the array were sorted from low to high and so I could use a binary search instead of the (usually but not always) less efficient linear search. Well what could be easier? After all, binary search is basic computer science 101. Because I was coding in C# I could use the built-in binary search method, for example:

int[] data = { 3, 5, 9, 11, 17 };
int target = 11;
int searchResult = Array.BinarySearch(data, target);
if (searchResult < 0)
  Console.WriteLine(“Target not in array”):
else
  Console.WriteLine(“Target is in array at index = ” + searchResult);

I remembered that coding a binary search method from scratch is surprisingly tricky so I thought I’d look up binary search on Wikipedia. I find most Wikipedia technical articles accurate and well-written but the article on binary search was very poor. I was surprised to see that the article presents a deliberately incorrect iterative (as opposed to recursive) algorithm but does not present a correct version. I sat down and wrote a few different versions of binary search, and, as I remembered, it was very tricky. In particular the main loop condition of “while (low < high)”. It’s not at all clear whether it should be < or <=. Also the update statements:

if (target > data[mid])
  low = mid + 1;
else
  high = mid – 1;

I’ve seen all kinds of variations using just mid, or mid + 1, or mid -1. And there are other subtleties too about when and how to check for the target-found condition. The moral is, binary search is very, very tricky and in my case at least I decided to use the built-in Array.BinarySearch method.