worst case it is nlogn, though only a carefully constructed list (as in zexi's post) will do so.

One way to avoid getting hit by these worst cases are using increasingly greedy search zone: first see if position n+2 is 2 larger, then n+4 is 4 larger, and n+8 is 8 larger... until you know the break point is in certain zone, within which you can do the bi-sec search.

By varying the greediness, you can rule out the possibility someone can construct a worst case example specific to your algorithm.

Overall, this is the best algorithm I saw on this question.

Technically, as we cannot assign probability to an increasing array, so it is pointless to talk about average performance. But in real world I would adopt the Op's algorithm