current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 4 down vote favorite

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.

share|improve this question
    
You can take a look into the implementation of the .net framework ;). – JanDotNet 18 hours ago
    
I am doing, but thank you. SourceOf.Net for the uninitiated – George Grainger 18 hours ago
    
Check the accepted answer here codereview.stackexchange.com/questions/152085/bisection-meth‌​od – Paparazzi 17 hours ago
1  
Aside from the speed, have you tried looking for eg int search = 50; ? – Henk Holterman 16 hours ago
up vote 5 down vote

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.

share|improve this answer
    
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. – Cody Gray 18 hours ago
    
@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. – Peter Taylor 17 hours ago
    
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. – Cody Gray 17 hours ago
    
@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 %. – Peter Taylor 15 hours ago
up vote 2 down vote

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;
int search = 55;            
bool found = false;

while (!found && searchStartInclusive < searchEndExclusive)
{
   // checked() to ensure an overflow will throw an exception
   int middle = checked( (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.

share|improve this answer
    
I prefer to accept the constraint sortedData.Length < int.MaxValue/2 rather than using unsigned int or complicating the calculation of middle here. – Henk Holterman 16 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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