A binary search with even amount of numbers

[millman]

In a binary search, with an even amount of numbers, will the algorithm choose the higher or lower middle number?

So if the array is:

15 18 18 21 26 31 36 38

Then will it start by looking at 21 or 26?

[Stewart Ross]

For an even-number of values N within a range being searched the mid-point is at value N/2, but the two 'halves' are of slightly different sizes. For N=8 the first value tested will be the fourth value, in your case 21. This leaves three values in the lower 'half', and four values in the upper half.

For an odd number of values N/2 would lie between two values. As a choice has to be made of what value to compare it is possible to either take the integer part of N/2 and ignore the decimal part (by using integer division), or round up the mid-point to the next-nearest value. With 9 values, for example, integer division would give a mid-point at value 4, with 3 values in the lower 'half' and five values in the 'upper'. Rounding up the mid-point leaves the lower and upper halves with the same number of values (four each in the case of 9 values overall).

For odd numbers, the small difference in choosing Int(N/2) as the mid point as opposed to Int(N/2)+1, say, makes very little difference in practice to overall performance as the chance of the value being searched for being in the current 'half' is more or less the same in both cases.

For further information, see for example this Wikipedia article

-Stewart