0
$\begingroup$

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.)

I have a (large) array of data, not completely sorted, but with which has a very precise structure, defined as follows.

The array has a length that is a (very large) power of 4.

The data is such that:

  • if the array is split in 4 parts - all of the same number of elements - then in each part the first element is the Minimum of this part, and the last element is the Maximum of this part (minimum < maximum).

  • if we take any one of these parts and, within it, we repeat the subdivision in 4 equal parts, the above fact holds always again for each of the new parts, all the way down, until we arrive at the smallest part, of size 4 elements.

(in other words a sort of "fractal" arrangement, we might perhaps say (?)).

Question:

I need to search this array for a given specific value.

  • What would be the most efficient algorithm to perform the search, given the above structure
  • And what is the best complexity I should expect for this task

(I would also like to know if this sort of problem is well known and has a name and there are additional pointers I can read read. Thank you)

$\endgroup$
  • 9
    $\begingroup$ Search can take $\Omega(n)$ time. Consider the array with $(n/2)-1$ 0's, $(n/2)$ 2's and one $1$. In the worst case, in every split, there is least a $0$ and a $2$ in each part. Only at the bottom split you can figure out where the $1$ is. $\endgroup$ – Chao Xu Apr 18 '14 at 19:32
  • 1
    $\begingroup$ @ChaoXu, I didn't understand your construction, where did you put that 1? But Pam, I think the problem as the way I understand it, is solvable in O(log n) by modifying binary search such that in each comparison compares given number with middle one and 4 number in the right and 4 number in the left of that middle number. By the way is better to provide a sample array. $\endgroup$ – Saeed Apr 18 '14 at 19:42
  • 3
    $\begingroup$ @Saeed I thought the split is the following operation: If the array is $a[0..4k-1]$ , the split to 4 parts are $a[0..k-1]$,$a[k..2k-1]$,$a[2k..3k-1]$ and $a[3k..4k-1]$. In this case 2020 will never appear as a part in my example. $\endgroup$ – Chao Xu Apr 18 '14 at 20:01
  • 8
    $\begingroup$ @Pam your structure is reminiscient of a heap (though it's not the same). In a heap you can find (and update) the min easily, but finding a specific item is not easy. That's the analogy for why your structure, while being "rigid", doesn't allow for quick search. $\endgroup$ – Suresh Venkat Apr 18 '14 at 22:51
  • 4
    $\begingroup$ @ChaoXu make that an answer ? $\endgroup$ – Suresh Venkat Apr 19 '14 at 8:16

Your Answer

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

Browse other questions tagged or ask your own question.