Searching through an unsorted array with a better than O(n) complexity?

Question

This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't even think of the answer myself.

They start with an unsorted array of integers and they're to find an element (there could be any number of them, guaranteed to be at least one) whose value is less than that of its neighbors, recursively.

Due to the nature of the problem the array can't be sorted, yet they asked them for a better than linear time solution. How could such a thing be?

He told me they explained binary search in class, but it doesn't apply, just like any other search algorithm based on sorted arrays; still, apparently he tried to do the assignment traversing the array (after all, numbers meeting that criteria could be anywhere, it's not like you can discard part of it), but his teachers added a couple of unit tests to ensure that the search algorithm is both recursive and not O(n).

They gave them two examples:

• [1, 2, 3, 4] -> Only the 1 would meet that criteria.
• [1, 3, 4, 1, 1] -> All three 1s would meet that criteria.

And they also gave them hints:

• It can be solved similarly to how binary search works, via divide and conquer, having the function receive the array, and two integers that mark the beginning and end of a subarrays.
• If the subarray size is 1, that's that location is good to go.
• If its size is 2, the biggest of them is the one.
• If its size is >= 3, you're to check the middle one and its neighbors, if it's smaller than the neighbors you're done, otherwise you'd choose the interval based on the comparison.

The emphasis is mine, but, what the hell?

I mean, if an array is size 2, let's say, [1, 2], the one being smallest should be the chosen index, not the biggest; leaving that aside though, given the description of the problem, how is that comparison going to allow you to discard some part of the array? Which partitions would you take when the whole thing is unsorted?

My days of working with these kinds of algorithms are long gone, but I couldn't figure out what they wanted them to do. Is there something I'm missing? How could this be of logarithmic complexity?

Answer 1

Your example $1,3,4,1,1$, in which you state that all $1$s are less than their neighbors, suggests that by "less than" you actually mean "at most". Any array contains an element whose value is at most that of its neighbors — just take any minimal value of the array.

As you mention, if the array has length $1$ or $2$ then the problem is easy (when the array is $x,y$, you choose the minimum of $x,y$). Given an array $A$ of length $n \geq 3$, let us split it as follows: $B, x, y, z, C$, where $B,C$ are subarrays of lengths $\lfloor \frac{n-3}{2} \rfloor, \lceil \frac{n-3}{2} \rfloor$. We consider three cases:

• If $y \leq x$ and $y \leq z$ then we choose $x$.
• If $y > x$ then we recurse on $B,x$, an array of length $\lfloor \frac{n-1}{2} \rfloor$.
• If $y > z$ then we recurse on $z,C$, an array of length $\lceil \frac{n-1}{2} \rceil$.

The procedure terminates in $\log_2 n$ steps, and so runs in time $O(\log n)$.

---

If you are actually looking for an element which is strictly less than its neighbors, you cannot do better than linear time. Indeed, consider any algorithm that makes at most $n-2$ queries. We run the algorithm, and whenever the algorithm accesses an array element, we always answer $1$. We claim that at the end, the array cannot output any index. Indeed, suppose that it inputs $i$. Since the algorithm makes at most $n-2$ queries, there is some index $j \neq i$ it hasn't queried. The queries made by the algorithm are consistent with an array in which $A[j] = 0$ and $A[k] = 1$ for all $k \neq j$, in which the only correct answer is $j \neq i$. Therefore at least $n-1$ queries are necessary.

Answer 2

You are right.

For example, if the array is:

      |  0  if i=52
a[i]= |  1  if 1<=i<=100 and i<>52

, it is impossible to use the binary search. You cannot recognize the half containing the single local minimum by a[] at its end and middle points. They all have the same meanings for both halves.

So, there is an error in the formulation of the task.

(BTW, it would be much better to put an exact formulation of the task in the question)