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.

• JanDotNet: You can take a look into the implementation of the .net framework ;).
• George Grainger: I am doing, but thank you. SourceOf.Net for the uninitiated
• paparazzo: Check the accepted answer here codereview.stackexchange.com/questions/152085/bisection-method
• Henk Holterman: Aside from the speed, have you tried looking for eg int search = 50; ?

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.

• Cody Gray: 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.
• Peter Taylor: @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.
• Cody Gray: 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.
• Peter Taylor: @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 %.

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.