def summaryRanges(self, nums):
:type nums: List[int]
res = 
i = 0
while i < len(nums):
temp = nums[i]
while i < len(nums)-1 and nums[i+1] - nums[i] == 1:
i += 1
if temp != nums[i]:
res.append(str(temp) + "->" + str(nums[i]))
i += 1
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