public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> list = new ArrayList<>();
for (int i = 0, len = nums.length, k; i < len; i = k + 1) {
k = help(nums, i, len);
if (i != k)
list.add("" + nums[i] + ">" + nums[k]);
else
list.add("" + nums[i]);
}
return list;
}
private int help(int[] nums, int l, int r) {
while (l + 1 < r) {
int m = (l + r) / 2;
if (nums[m]  nums[l] == m  l)
l = m;
else
r = m;
}
return l;
}
}
My java 0ms(not always Luckily !You are here! Your runtime beats 97.90% of java submissions.)


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 bisec 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