Binary Search c#

Question

Here's my attempt at a binary search algorithm:

int[] intArr = new int[11] { 0, 5, 13, 19, 22, 41, 55, 68, 72, 81, 98 };
int search = 55;            
bool found = false;

while (!found)
{
   // if array is of length 1, and number does not equal search value, break
   if (intArr.Length == 1 && intArr[0] != search)
      break;
   // if the midpoint number of the array is less than that you are searching for
   else if (intArr[(int)Math.Round((decimal)intArr.Length / 2, MidpointRounding.AwayFromZero) - 1] < search)
      // return the latter half of the remaining array
      intArr = intArr.Skip((int)Math.Round((decimal)intArr.Length / 2)).ToArray();
   // if the midpoint number of the array greater than that you are searching for
   else if (intArr[(int)Math.Round((decimal)intArr.Length / 2, MidpointRounding.AwayFromZero) - 1] > search)
      // return the former half of the remaining array
      intArr = intArr.Take((int)Math.Round((decimal)intArr.Length / 2, MidpointRounding.AwayFromZero)).ToArray();
   else
      found = true;
}

if (found)
    Console.WriteLine("Search number is: {0}",
      intArr[(int)Math.Round((decimal)intArr.Length / 2) - 1]);
 else
    Console.WriteLine("Number not found in collection");

Console.ReadLine();

What can I do to speed-up/optimise my implementation? Testing it against the internal BinarySearch method, mine was 90 times slower!

Edit

It was pointed out that I hadn't included handling for search values not contained within the array. I've since added that, trying to conform to my original thought process. I will add the other suggested optimizations later and post the full refactored code.

Answer 1

Only 90? I'd expect worse!

intArr.Skip(...).ToArray(); is really quite slow. In the worst case that's going to copy about as many elements are there are in the original array, which means that you've lost the benefit of using a binary search instead of a linear one. If you want to use this conceptually simple approach to binary search then you will get much better performance from new ArraySegment<int>(intArr, ..., ...).

However, the standard approach to binary search doesn't bother with wrapping anything round the array. Instead it keeps two variables to represent the subarray and moves them towards each other until the value is found or the range is empty. (Incidentally that case seems to be missing: does your code have a bug when the value isn't in the array?)

---

Another much more minor optimisation is to ditch (int)Math.Round((decimal)intArr.Length/2) and use instead (intArr.Length + 1) / 2. Also, as a style improvement rather than a speed one, pull the reused value out into a local variable. That's a long enough expression that it would probably be worth pulling out if only used once: it's definitely worth pulling out when used three times.

Answer 2

Here's my attempt at a binary search

Binary search is an excellent choice for learning about algorithms, but you have to get it right.

You can help yourself a lot by picking the right names and variables. Your found is a good example but it's not enough. I suspect your version to fail when the search item is not in the data. So you need to set up the conditions "not found" and "still some area to search in"

int[] sortedData = new int[] { 0, 5, 13, 19, 22, 41, 55, 68, 72, 81, 98 };
int searchStartInclusive = 0;
int searchEndExclusive = sortedData.Length;     
bool found = false;

int search = 55;       

while (!found && searchStartInclusive < searchEndExclusive)
{
   // simple version, might overflow for very large arrays.
   int middle = (searchStartInclusive + searchEndExclusive) / 2;

   // Invariant: 0 <= middle < sortedData.Length
   ...
}

Try to finish the algorithm by adjusting searchStartInclusive or searchEndExclusive in each step. No need to copy the array data around.
Also, the index of the searched-for item is probably much more interesting then that number itself.