# Most efficient algorithm to search an unsorted array with a very precise data structure

(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)

• 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. – Chao Xu Apr 18 '14 at 19:32
• @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. – Saeed Apr 18 '14 at 19:42
• @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. – Chao Xu Apr 18 '14 at 20:01
• @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. – Suresh Venkat Apr 18 '14 at 22:51
• @ChaoXu make that an answer ? – Suresh Venkat Apr 19 '14 at 8:16