[sischoel]

It is indeed O(N). There is also a more efficient algorithm (in case the range is small) that uses binary search to find the first index. Such an algorithm would have time complexity O(log(N) + H) where H is the number of elements in the output.