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