Array Binary Search is Tricky

When I’m coding in a .NET environment and I need to search a sorted array, I usually use the built-in Array.BinarySearch, for example:

long[] array = new long[] { 0, 11, 22, 33, 44, 55};
long target = 22;
int result = Array.BinarySearch(array, target);
if (result < 0) Console.WriteLine(“not found”);
else Console.WriteLine(“found at index ” + result);

But sometimes I need to code up binary search (usually when I need to customize the search in some way). Well the bottom line is that binary search is very tricky to code correctly. There are dozens of variations on the implementation of binary search. Here’s the version I start with:

static int BinarySearch(long[] array, long target)
  int low = 0;
  int high = array.Length – 1;
  int mid = 0;
  while (low < high)
    mid = low + ((high – low) / 2);
    if (target > array[mid])
      low = mid + 1;
      high = mid;

  if (array[high] == target) return high; else return -1;

The binary search algorithms are ultra-sensitive in the sense that there is almost no room for variation. For example, if low = mid + 1 is changed to low = mid the code can go into an infinite loop for some inputs. Somewhat surprisingly, this version of binary search always terminates with the condition that low == high so the condition if (array[high] == target) could be changed to if (array[low] == target). The moral is: use a built-in binary search if possible, but if you do have to code a custom binary search, be very, very careful.

This entry was posted in Software Test Automation. Bookmark the permalink.