Locate all locations in a sorted array where arr[i]<arr[i+1] Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor.
For example, given the array $arr={3,3,5,5,5,200,200,200,200,209}$, the output would be: ${2,5,9}$.
Obviously, this can be done in linear time. I am trying to improve upon this using a binary search.
Let $k$ be the number of output locations. In $O(k \log n)$ time we can get our answer. To find first location, check locations $2,4,8,$etc. Suppose you find that $arr[1]&lt;arr[2^{j}$], recursively search the interval from $2^{j-1}$ to $2^j$-1.

My QUESTION: In the worst case, $k=O(n)$. I do NOT want to ever pay
$O(n \log n)$ since the naive algorithm is $O(n)$. However, I do not pay $O(n \log n)$ for $k=O(n)$ since the binary searches terminate in $O(1)$ time. 
How do I prove that the algorithm is worst case $O(k \log n)$ when $k &lt;&lt; n$ and never worse than $O(n)$?
Here is a fairly simple fix. Anytime you "overshoot" in your search (I.e. $A[i]=A[i+2^j]$ but $A[i] \neq A[i+2^{j+1}]$ when you backtrack to find the correct index, also keep track of elements in that range that satisfy the inequality (may as well if your scanning over them anyway). You can pick back up at $A[i+2^{j+1}]$. This way, your running time is $O(n)$ worst case.