5
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The length should probably be cast to an unsigned value for the addition and division operations, otherwise you run the risk of overflow in an edge case where the array's length is already Int32.MaxValue. This will also be slightly faster. \$\endgroup\$ – Cody Gray Jan 23 '17 at 17:00
  • \$\begingroup\$ @CodyGray, interesting point, although really the better solution to the overflow is to not increment. Why do you think it will be faster? I would expect it to compile down to the same operations. \$\endgroup\$ – Peter Taylor Jan 23 '17 at 17:09
  • \$\begingroup\$ Nah, it can't be the same operation. An unsigned division by 2 will be optimized to a right shift by 1. The same can't be done for a signed value; special care must be taken to compensate for the signedness. In general, you'll get an unsigned right-shift to isolate the sign bit, this is added to the original value, and then a signed right-shift will be performed to actually do the division. This is what a C/C++ compiler would do, and the C# JIT compiler will do the same thing. Of course, this all assumes x86; on other processors, it is very likely different, but the same general logic applies. \$\endgroup\$ – Cody Gray Jan 23 '17 at 17:52
  • \$\begingroup\$ @CodyGray, ah, I forgot about round-towards-zero division. Where possible I favour languages which consistently round towards negative infinity and so always give positive results from %. \$\endgroup\$ – Peter Taylor Jan 23 '17 at 19:11
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.