Some of the results  make sense but the weird ones are March, May, October and
November. Obviously the algorithm says they are not in the list but why, when
it can find June, and why does it then think it should choose August rather
than April.

July seems to give the logical answer because March is greater, so it takes
the previous value. But, if so, why is June not treated the same way?

It probably speeds the search by looking at halfway (June) first, If the item
is higher it looks at halfway between there and the end (September). This
means that all items between June and September alphabetically are reported as
August. Similarly July is compared with June <
March <
February > so February is selected.