HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Binary Search c#

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
binarysearchstackoverflow

Problem

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

Solution

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

Context

StackExchange Code Review Q#153402, answer score: 6

Revisions (0)

No revisions yet.