4
$\begingroup$

If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have those bounds in A for each subarray), with the following conditions:

min(i) < min(i+1),
max(i) < max(i+1),
min(i+1) < max(i),
If subarrays A(i) and A(i+1) both have the j-th element, then A(i,j) < A(i+1,j),
The number of elements in subarray A(i) is strictly increasing with i

Would it be possible to search an element in the array $A$, in time $O((\log N)^k)$, for a positive $k$? If yes how?

If not, what kind of minimal additional conditions would allow that?

Edit. The subarrays are not necessarily of equal length. They are strictly increasing. The above stated conditions are always guaranteed.

What I have tried so far is to binary search them separately, but that is obviously going to be very inefficient.

[Note that this question has obviously nothing to do with the search of the min of max value in the array. And I am not interested in sorting the array. Just the mere search.]

$\endgroup$
  • 3
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – Pål GD Aug 18 '13 at 20:03
  • $\begingroup$ So far i tried to search in the subarrays, but it seems way too inefficient. I'd like to have a global logarithmic search time. How could I achieve that ? $\endgroup$ – Pam Aug 18 '13 at 21:50
  • $\begingroup$ How inefficient? Could you find a possibly non-constant $k$ that works? I.e., depending on $N$. Or, asked slightly differently, which running time did you get? $\endgroup$ – Pål GD Aug 18 '13 at 23:01
  • $\begingroup$ Of course I obviously get O(sqrt(N) log(N)). $\endgroup$ – Pam Aug 19 '13 at 0:07
  • $\begingroup$ What do you know about the adjacent subarrays? Are they all of length $\sqrt{N}$? Could they be of any length? Are we guaranteed that all of the subarrays are monotonically increasing, or could each one be either monotonically increasing or decreasing (no promises, they might each be different)? Are the subarrays guaranteed to be strictly increasing/decreasing (so no adjacent elements are equal)? Please edit your question to make the problem statement more precise and to show us what you've tried. $\endgroup$ – D.W. Aug 19 '13 at 0:22
1
$\begingroup$

It should be possible to do this with $O(\sqrt{N})$ comparisons, saving an $O(\log N)$ factor over the straightforward "binary search each subarray".

The last condition, that the lengths of the subarrays strictly increases, makes things messy. The analysis of $M$ subarrays, each of length $M$, is easier and it should be straightforward to extend the method to increasing-length subarrays. Note that $\log M = O(\log N)$.

Also complicating things are the strict inequalities; it is easier to work with non-strict inequalities (which are also more general).

Finally, the conditions ensure that in subarray $A(i)$, the first element $A(i,1)$ is the minimum value and the last element $A(i,M)$ is the maximum value, so there is no need to deal with these elements explicitly. This yields the simplified problem

  1. there are $M$ subarrays of equal length $M$, and

  2. for all $i,j$

    • [monotonicity across subarrays] $A(i,j) \le A(i+1,j)$,
    • [adjacent subarrays overlap] $A(i+1,1) \le A(i,M)$, and
    • [monotonicity within subarrays] $A(i,j) \le A(i,j+1)$.

If there is $u$ such that $A(u,1) \le n < A(u+1,1)$, then only the first $u$ subarrays need to be considered, and similarly for $v$ such that $A(v-1,M) < n \le A(v,M)$ focuses attention on the last $v$ subarrays; together their intersection defines a set of subarrays that must contain $n$. The rest of the subarrays can be ignored. This preprocessing can be done in $O(\log N)$ steps.

Then $A(i,1) \le n \le A(i,M)$ is guaranteed for each remaining $i$ in the range $M-v+1$ to $u$, otherwise $n$ is not in the array. For the remainder, suppose that the preprocessing did nothing, so $u=v=M$ (this is the worst case). Run binary search on the middle subarray $w=\lfloor M/2\rfloor$; this determines that $A(w,j) < n < A(w,j+1)$; (if equality holds then $n$ has been found).

By monotonicity across subarrays, $A(i,j) \le A(w,j) < n$ for all $i \le w$ and similarly $n < A(w,j+1) \le A(i,j+1)$ for all $i \ge w$.

Now we need to recursively search about half of the remaining elements, considering the two rectangular blocks $A(1,j+1)..A(w-1,M)$ and $A(w+1,1)..A(M,j)$ in turn. There are $M$ calls to check a block, but successive calls receive exponentially smaller blocks to work with. Amortising the work across calls, the total work is $O(\sqrt{N})$ steps as each leaf of the search tree only does a constant amount of work. More precisely this relates to solving the recurrence $f(n) = 2f(n/4) + \log n$ for which $f(n) \in O(\sqrt{n})$.

So overall, $O(\sqrt{N})$ steps suffice.

Note that the overlap of adjacent subarrays may be of use when extending to increasing-length subarrays, or in improving the algorithm, but isn't used here.

As far as I can tell, $\Omega(\sqrt{N})$ is also a lower bound. A handwaving argument is that in the worst case, when all the values are close except for a single missing value, that value could be hidden in any of the rows and each row must be examined at least once.

$\endgroup$
  • $\begingroup$ I think the critical point here is that "each leaf of the search tree only does a constant amount of work" unfortunately does not hold true. In fact the number of elements you will be searching in each block is also a function of N, and not a constant. Practically, if we picture the subarrays one "on top of the other" (say like a pyramid) you are intuitively removing at each step either the top left "rectangle" or the bottom right "rectangle"... $\endgroup$ – Pam Aug 20 '13 at 9:59
  • $\begingroup$ ... Problem is that at each removal you create a new split in 2 parts, each of which has to be searched and each of which has a number of element which depends on N. So we only make the search process more complicate due to recursion, I think. Am I right ? $\endgroup$ – Pam Aug 20 '13 at 9:59
  • $\begingroup$ Problem is not recursion, but that the subsets you consider for search at each step depend on N and therefore they not not take constant time. (It's obvious they cannot take constant time, as, if so, they could not add up to N elements of A.) So you essentially end up with same complexity of my naive approach (but an algo more difficult to implement). I think. $\endgroup$ – Pam Aug 20 '13 at 14:18
  • 1
    $\begingroup$ The solution to the recurrence $f(n) = 2f(n/4) + \log n$ is an expression that is $O(\sqrt{n})$. Do you disagree that this characterizes the runtime of the algorithm? $\endgroup$ – András Salamon Aug 20 '13 at 18:52
  • 1
    $\begingroup$ As I stated, it seems to me that $\Omega(\sqrt{N})$ is a lower bound. I don't have time right now to develop a full communication complexity reduction, but this seems eminently doable. $\endgroup$ – András Salamon Aug 20 '13 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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