Locate all locations in a sorted array where arr[i]<arr[i+1]
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.