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

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

<p>The array has a length that is a (very large) <strong>power of 4</strong>.</p>

<p>The data is such that:</p>

<ul>
<li><p>if the array is split in 4 parts - all of the <strong>same number of elements</strong> - then <strong>in each part</strong> <strong>the first element is the Minimum</strong> of this part, and <strong>the last element is the Maximum of this part</strong> (minimum &lt; maximum).</p></li>
<li><p>if we take <strong>any one of these parts</strong> 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.</p></li>
</ul>

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

<p><strong>Question:</strong></p>

<p>I need to search this array for a <strong>given</strong> specific value.</p>

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

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

CC BY-SA 3.0
2014-04-18T19:32:32.493Z
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
CC BY-SA 3.0
2014-04-18T19:42:05.463Z
@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
CC BY-SA 3.0
2014-04-18T19:46:36.043Z
Thank you @Chao Xu. So are you practically saying that he knowledge of this "strict" structure in the data is of no "help" at all for the search ? (The splitting can be done in logarithmic time, right?)
Pam
CC BY-SA 3.0
2014-04-18T19:49:21.737Z
@Saeed A concrete example: 02020202...0212, in every split except the last level, the first element in each part is 0, last element is 2.
Chao Xu
CC BY-SA 3.0
2014-04-18T19:52:39.413Z
@ChaoXu, Consider this portion of your sample : 2020, it does not satisfy OPs constrains. (or I misunderstood the constrains).
Saeed
CC BY-SA 3.0
2014-04-18T19:52:59.470Z
Thank you @Saeed. My first though (or hope) was actually that some form of "modified" binary, as you mention, (or using 4 splits at a time) search could work. (But naively splitting simply in 4 each time did not seem to work.)
Pam
CC BY-SA 3.0
2014-04-18T20:01:50.483Z
@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
CC BY-SA 3.0
2014-04-18T20:07:25.390Z
@Saeed ChaoXu, I tried to generate a tiny example:  0, 0, 0, 1, 0, 0, 2, 3, 0, 2, 0, 3, 4, 6, 6, 9, 0, 0, 4, 5, 0, 0, 6, 7, 8, 10, 12, 15, 12, 14, 18, 21, 0, 4, 0, 5, 8, 12, 10, 15, 0, 6, 0, 7, 12, 18, 14, 21, 16, 20, 20, 25, 24, 28, 30, 35, 24, 30, 28, 35, 36, 42, 42, 49, I hope I got it right.
Pam
CC BY-SA 3.0
2014-04-18T20:08:28.790Z
@ChaoXu, Seems you are right. About the recursive part I thought may be we can take random part of array, but when I reread it, seems we cannot. So your answer is correct. and now with ops sample, is more clear that we cannot.
Saeed
CC BY-SA 3.0
2014-04-18T20:09:45.043Z
@Pam, as Chao pointed out you cannot do search better than $\Omega(n)$.
Saeed
CC BY-SA 3.0
2014-04-18T20:12:52.457Z
@Saeed, Yep it does seem so. It's pretty weird that the rigid structure is there and it can't really improve the search.
Pam
CC BY-SA 3.0
2014-04-18T22:51:46.540Z
@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
CC BY-SA 3.0
2014-04-19T08:16:58.553Z
@ChaoXu make that an answer ?
Suresh Venkat
CC BY-SA 3.0
2014-04-19T10:13:51.947Z
@Suresh Venkat Thank you, nice analogy. Maybe the point is try to intervene on the data generation process itself, to have the terms minimally rearranged, so that the search can be improved.
Pam
CC BY-SA 3.0
2014-04-19T13:29:31.963Z
@ChaoXu Would my situation improve if I add the following rules to the data structure: min1<min2<min3<min4 and max1<max2<max3<max4 when the min and max are those of the 4 parts into which *each* part can be split, and then also assume the elements to be all positive non prime integers?
Pam
CC BY-SA 3.0
2014-04-19T17:36:44.590Z
@Pam that mod won't help. The problem is that the intervals of interest can still maximally overlap, and so it's still possible to "hide" an entry in between. You need the different subproblems to cover (roughly) disjoint regions of space to get a nontrivial improvement.
Suresh Venkat
CC BY-SA 3.0
2014-04-19T18:06:45.003Z
@Suresh Venkat I get it, you are right. Thank you very helpful.
Pam
<ds.algorithms><time-complexity><search-problem><fractals><binary-space-partitions>
Most efficient algorithm to search an unsorted array with a very precise data structure
Pam
# Most efficient algorithm to search an unsorted array with a very precise data structure

(Asked by: username_0 on 2014-04-18)

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

**Tags:** ds.algorithms, time-complexity, search-problem, fractals, binary-space-partitions
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_0**: Thank you @Chao Xu. So are you practically saying that he knowledge of this "strict" structure in the data is of no "help" at all for the search ? (The splitting can be done in logarithmic time, right?)  
> **username_1**: @Saeed A concrete example: 02020202...0212, in every split except the last level, the first element in each part is 0, last element is 2.  
> **username_2**: @ChaoXu, Consider this portion of your sample : 2020, it does not satisfy OPs constrains. (or I misunderstood the constrains).  
> **username_0**: Thank you @Saeed. My first though (or hope) was actually that some form of "modified" binary, as you mention, (or using 4 splits at a time) search could work. (But naively splitting simply in 4 each time did not seem to work.)  
> **username_1**: @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.  
> **username_0**: @Saeed ChaoXu, I tried to generate a tiny example:  0, 0, 0, 1, 0, 0, 2, 3, 0, 2, 0, 3, 4, 6, 6, 9, 0, 0, 4, 5, 0, 0, 6, 7, 8, 10, 12, 15, 12, 14, 18, 21, 0, 4, 0, 5, 8, 12, 10, 15, 0, 6, 0, 7, 12, 18, 14, 21, 16, 20, 20, 25, 24, 28, 30, 35, 24, 30, 28, 35, 36, 42, 42, 49, I hope I got it right.  
> **username_2**: @ChaoXu, Seems you are right. About the recursive part I thought may be we can take random part of array, but when I reread it, seems we cannot. So your answer is correct. and now with ops sample, is more clear that we cannot.  
> **username_2**: @Pam, as Chao pointed out you cannot do search better than $\Omega(n)$.  
> **username_0**: @Saeed, Yep it does seem so. It's pretty weird that the rigid structure is there and it can't really improve the search.  
> **username_3**: @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.  
> **username_3**: @ChaoXu make that an answer ?  
> **username_0**: @Suresh Venkat Thank you, nice analogy. Maybe the point is try to intervene on the data generation process itself, to have the terms minimally rearranged, so that the search can be improved.  
> **username_0**: @ChaoXu Would my situation improve if I add the following rules to the data structure: min1<min2<min3<min4 and max1<max2<max3<max4 when the min and max are those of the 4 parts into which *each* part can be split, and then also assume the elements to be all positive non prime integers?  
> **username_3**: @Pam that mod won't help. The problem is that the intervals of interest can still maximally overlap, and so it's still possible to "hide" an entry in between. You need the different subproblems to cover (roughly) disjoint regions of space to get a nontrivial improvement.  
> **username_0**: @Suresh Venkat I get it, you are right. Thank you very helpful.  

---

## 0 answers

