Although the other answers made some good stylistic observations and suggestions for improvement, many have missed a critical bug lurking in this code. Here's the offending line—see if you can spot it:
middle = (left + right) / 2;
See it? Probably not; most programmers don't, and that's why it is so common. The problem here is that the addition operation (
left + right) can potentially overflow. There are many different values for
right that could cause this to happen; it simply requires that their sum be larger than the maximum positive value representable by
int, which is
Int32.MaxValue, or 231−1.
In C#, there are a couple of different possibilities for how overflow is dealt with. If the values are constant and the compiler can catch it at compile-time, you'll get a compile-time error, unless you are performing the operation inside an
unchecked block. If it can't be detected at compile time, then you will either get an
OverflowException thrown (if the code is in a
checked context, which is coincidentally always the case in VB.NET) or you will get two's-complement style (modulo 2n) wraparound (if in an
unchecked context, which is the default in C#).
So although you aren't dealing with any scary undefined behavior, this is still a bug. Depending on your compiler settings, you will either get an exception (which you don't handle), or you will end up with a negative intermediate value that, when divided by 2, will give the wrong value for
middle, deferring the exception until such time as you try and use
middle to index into the array.
Note that the final result for
middle should never overflow the representable range for an
int, since you're dividing by 2. That's what makes this bug so insidious and difficult to detect. The code looks like it is correct. The problem manifests only in the intermediate value obtained after doing
left + right, since you aren't using an infinite-precision type. This is easy to miss.
You won't run into this bug at the top of your function, where you first declare and initialize
middle. Why not? Look at the code:
int left = 0;
int right = array.Length - 1;
int middle = (left + right) / 2;
You know that
left is 0, and you know that
right is less than the maximum positive value representable by an
int, so there is no possibility for overflow. In fact, the compiler sees this as simply
middle = (array.Length - 1) / 2;.
You are not so lucky inside of the
while loop, though. There, if the value you seek is in the second half of the array, you'll end up assigning
left, and then if the array is sufficiently large (i.e., if
right is sufficiently large), then the calculation of
middle will overflow as described.
Perhaps not terribly likely that you'll have an array large enough (famous last words!), but still a bug waiting to strike when you least expect it.
One possible solution is to rearrange the computation so that you do the division before the addition. This alleviates the possibility of an overflow, but results in the following somewhat inscrutable code:
int middle = low + ((high - low) / 2);
This works, but aside from the readability concerns (which could be addressed by a comment), it is slower than the original. Even an optimizing compiler has little choice but to transform this into a nearly-literal sequence of machine instructions.
A better solution is to do the computation with an unsigned integer value (in an unchecked context, of course). That way, you'll get the wrap-around behavior as desired, and the integer being treated as unsigned ensures that the result won't be interpreted as a negative value. The code remains essentially what you had, except with the addition of some ugly casts to force the intermediate arithmetic operations to be done on an unsigned integer, and then to cast the result back to a signed integer:
int middle = (int)(((uint)low + (uint)high) / 2);
Some people will write this with a right-shift operator, e.g.:
int middle = (int)(((uint)low + (uint)high) >> 1);
but that is unnecessary and doesn't buy you anything. In C# (unlike Java), there is no explicitly unsigned right-shift operator (i.e., one that does zero-extension as opposed to sign-extension), so the casts are still required. And once you've got the casts to force an unsigned arithmetic operation, you might as well just do a division. Let the JIT compiler optimize an unsigned division by a constant 2 into an unsigned right-shift by 1—and indeed, it will do precisely that, allowing you to write the code so that it remains readable and correct.
You probably still want a comment to ensure that an overzealous maintenance programmer doesn't remove the "superfluous" casts.
Although you could convert the numbers into a floating-point space to increase the range, this will be slower—probably significantly so in a tight loop. Since it is not necessary and the problem is trivially solved by using unsigned integers, I recommend not doing this.