Locate all locations in a sorted array where arr[i]<arr[i+1]

Question

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]<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 << n$ and never worse than $O(n)$?

Answer 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.

Answer 2

In fact you need start binary search $k$ times. Assuming, you use divide & conquer techniques (after found one location x_i, start binary search on x_0..x_i-1 and x_i..x_n separately), algorithm will have runtime $O(n)$.

Algorithm would look as follows:

Search(low, high)
    mid = (low + high) / 2;
    if A[mid] == A[mid - 1]
    {
        if (A[low] < A[high])
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }
    else 
    {
        print k_i
        if (low < high)
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }

You can see we have $p=O(\log n)$ depth of recursion. Each call takes $O(1)$ operations and we have $2^p = O(n)$ calls. Graph of recursive calls would never have more than $O(n)$ vertices since each pair of neighboring elements is compared only once (or not compared at all).

Answer 3

A crude argument would be that you dereference a pointer in the array a constant number of times (depending on how you code it...), and hence the asymptotic complexity is at most linear in the input array.

If you want to seek a more formal direction to prove this worst case bound, I suggest you to read about amortized analysis and use its' tools.

Amortized Analysis - Wikipedia

Answer 4

Let's say your algorithm is roughly: Let k = 0. Then repeatedly either find the smallest k' > k such that arr [k] < arr [k'], or prove that none exist. If you find k', output k' - 1, let k = k', and repeat the search.

You need an algorithm that achieves the following: 1. In the worst case, finding k' takes O (log n). 2. The number of steps finding k' is at most O (k' - k).

I think you can't guarantee n comparisons (because to guarantee this, you need to compare arr [k] < arr [k+1] first in case all elements are different, then arr [k] < arr [k+2] in case every second element is different, then arr [k] < arr [k+3] in case every third element is different and so on).

You can achieve this with a guarantee of at most say 1.5n comparisons, if you grow the indices slowly initially.