2
$\begingroup$

Given an array $A$ of integers in ascending order, how efficiently can it be decided whether there exists an integer $i$ such that $A[i] = i$? How would an optimal algorithm for this problem work?

$\endgroup$
3
  • 1
    $\begingroup$ Hello, and welcome to Computer Science Stack Exchange! I have edited your question to be more suitable for this site; that said, as it is, this question doesn't really provide very much specific information. You can help the community better respond to your needs by explaining what you've tried, how you understand the problem, and any doubts or concerns you may have about your own method of resolution. As you are able, please take the time to edit your question to include more details. Thanks for contributing and, again, welcome! $\endgroup$
    – Patrick87
    Mar 27 '14 at 17:41
  • $\begingroup$ Recast it as "I'm looking for 0 in the array of the A[i] - i" and use binary search... $\endgroup$
    – vonbrand
    Mar 30 '14 at 2:30
  • $\begingroup$ Ascending, or nondescending? That is, is $A$ allowed to contain duplicates? The problem is clearly O(n) if duplicates are allowed (consider A[i] := i + 1), and O(log n) otherwise. $\endgroup$
    – ecatmur
    Mar 30 '14 at 19:05
7
$\begingroup$

It can be done in $O(\log~n)$ for a $n$ element array $A$ by using a slightly modified version of binary search. This is possible because you stated that the input array is made of increasing integers and is therefore sorted. It does not matter what kind of integers your input actually contains: the integers may be negative, zero or positive as long as the array is sorted.

Your search for an index $i$ such that $A[i] = i$ is of course equivalent to searching for an index $i$ such that $A[i] - i = 0$ and the function $f(i) = A[i] - i$ is monotonically increasing so that the problem reduces to finding, if it exists, one point $i$ where the function value is zero. It follows that you are guaranteed that if a check fails you only have to explore one subarray, which leads to $O(\log~n)$ in the worst case.

Your algorithm starts by checking the middle element as usual. If the check succeeds (A[middle] - middle = 0), you have found the index you are searching for. If $A[middle] - middle < 0$, then you need to check the right subarray; otherwise ($A[middle] - middle > 0$), you have to check the left subarray.

$\endgroup$
6
  • $\begingroup$ Beautiful concept!! just for clarification, isn't the function $f(i)$ monotonically decreasing? (i might be wrong though :) ) $\endgroup$
    – Subhayan
    Mar 27 '14 at 17:51
  • $\begingroup$ I think i was wrong earlier.. the function $f(i)$ is just convex it seems... consider an array $[3,3,3,5,7,9]$ $\endgroup$
    – Subhayan
    Mar 27 '14 at 18:00
  • $\begingroup$ @Subhayan, the function is monotonically increasing indeed. To see why, consider a generic index $i$. The next index $i+1$ differs from $i$ by exactly one; on the other hand, $A[i+1]$ differs from $A[i]$ by at least one owing to the fact that, by assumption, the input integers are increasing. Therefore, $A[i]−i$ is monotonically increasing. $\endgroup$ Mar 27 '14 at 18:04
  • $\begingroup$ he said ascending .. so an array like $[3, 3, 3, 5, 7, 9,13, 14, 14, 14, 14]$ satisfies.. however f(n) for this would be $[3,2,1,2,3,4,7,7,6,5,4]$ .. which is not monotonic or convex (this will be embarrassing if i am wrong, but will be happy if your concept works :) ) $\endgroup$
    – Subhayan
    Mar 27 '14 at 18:09
  • $\begingroup$ @Subhayan, the question has been edited. When I answered the question, the original question only stated that the integers were increasing. Therefore, no duplicated were allowed in the original question. $\endgroup$ Mar 27 '14 at 18:10
4
$\begingroup$

Let $lb, ub \in \mathbb N$ denote the lower and upper bounds of $A$, resp.

You are testing for the existence of an $i \in \{lb, \dots, ub\}$ such that $A[i]=i$ (a 'fixpoint element'). Solve the task by recursive bisection, ie. repeatedly halving the size of the array portion within which a fixpoint element may reside.

The basic idea of the algorithm consists in finding a slice of contigous array elements where the first element is less than its index while the last element is greater than its index. Since the elements in the array are strictly increasing, this is a necessary condition for the array slice to contain a fixpoint element (it's not sufficient though, consider $A[0..1] = <-a,a>, a > 1$).

In pseudocode

fn hasfix ( A: array int of int, lb: int, ub: int ): boolean =
    if lb = ub
        then return (A[lb] = lb)
        else if A[lb] > lb or A[ub] < ub
                 then false
                 else let m := floor ( (ub + lb) / 2 )
                       in if (A[m] < m)
                              then hasfix ( A, m+1, ub )
                              else hasfix ( A, lb , m  )
                          end if 
             end if
    end if
end

the initial call

hasfix ( A, lb, ub )

will indicate whether there is a fixpoint element. Giving the index of such an element is an obvious extension.

Running time of the algorithm is $O(\log n)$ for $n$ being the number of array elements. Note that you abstract away from the magnitude of the array limits, ie. the size of their representation, and thus assume that access to any array element is $O(1)$.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.