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?