<p>(I tried to ask at <a href="https://stackoverflow.com/questions/18014624/constant-time-search">SO</a> but maybe this has more to do with the CS theory.)</p>

<p>Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it belongs to, in constant time?</p>

<p>For example:</p>

<pre><code>  |------------------|---------|---------------|
  0.0                4.5       7.853293843     9.123
</code></pre>

<p>Given a position:</p>

<pre><code>                                   ^
                                   |
                                   8.005
</code></pre>

<p>I would like to get <code>3rd piece</code>.</p>

<p>It is possible to easily get such answer in O(log n) time with binary search but is it possible to do it in O(1)? If I pre-process the "cut" positions somehow? Perhaps there is a data structure which could help to speed the search up?</p>

<p>PS: Is there a name for such problem? I know "rod cutting" refers to a slightly different problem...</p>

CC BY-SA 3.0
2013-08-02T15:38:35.700Z
I don't know of a method for this exact problem, but the alias method (a way of generating elements randomly with given probabilities) does give a length-preserving constant-time map from positions to pieces, but possibly with a scrambled order of the pieces.
David Eppstein
CC BY-SA 3.0
2013-08-02T16:11:23.810Z
@DavidEppstein Thanks for the reply! I'm not familiar with "alias method" but from what I just read, doesn't it work in opposite direction? That is, if I have a segment it can generate some position?
Ecir Hana
CC BY-SA 3.0
2013-08-02T20:06:56.027Z
One interpretation of the alias method is that it scales and reorders the segments so that the segment containing a particular value $x$ can be determined in two steps: rounding $x$ to an integer, and then comparing the fractional part of $x$ against at most one segment boundary that lies between that integer and the next. So then you can generate a random segment by generating a random $x$ and applying this test.
David Eppstein
CC BY-SA 3.0
2013-08-05T02:55:44.383Z
It depends on your computational model. Suppose for example that the pieces have sizes $1/2,1/4,1/8,\ldots,1/2^n,1/2^n$ ($n$ pieces in total). Can you solve your problem in your case in $O(1)$?
Yuval Filmus
CC BY-SA 3.0
2013-08-05T02:57:45.047Z
The alias method can generate a random segment from the rod in proportion to its length. As David mentions, to that end it cuts the large segments (those larger than $1/n$) into pieces and reorders them; the pieces are not contiguous. In the end, each part of length $1/n$ will consist of a piece of a large segment, and possibly a small segment.
Yuval Filmus
CC BY-SA 3.0
2013-08-11T08:02:14.777Z
How do you find this approach:
David G
CC BY-SA 3.0
2013-08-11T08:11:09.770Z
What if you first pre-process the cut positions in such a way, that you can get the desired answer by reading the input bit-by-bit? In your example, you read 8 and this gives 3rd piece. If the input would be 7.852, the algorithm would in first three steps return the position 2-3 and in the next step (after reading digit 2) the answer would be 2.
David G
<ds.algorithms><time-complexity><search-problem>
Constant time search for rod segment
Ecir Hana
# Constant time search for rod segment

(Asked by: username_0 on 2013-08-02)

(I tried to ask at [SO](https://stackoverflow.com/questions/18014624/constant-time-search) but maybe this has more to do with the CS theory.)

Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it belongs to, in constant time?

For example:

```
  |------------------|---------|---------------|
  0.0                4.5       7.853293843     9.123

```

Given a position:

```
                                   ^
                                   |
                                   8.005

```

I would like to get `3rd piece`.

It is possible to easily get such answer in O(log n) time with binary search but is it possible to do it in O(1)? If I pre-process the "cut" positions somehow? Perhaps there is a data structure which could help to speed the search up?

PS: Is there a name for such problem? I know "rod cutting" refers to a slightly different problem...

**Tags:** ds.algorithms, time-complexity, search-problem

> **Comments:**
> **username_1**: I don't know of a method for this exact problem, but the alias method (a way of generating elements randomly with given probabilities) does give a length-preserving constant-time map from positions to pieces, but possibly with a scrambled order of the pieces.  
> **username_0**: @username_1 Thanks for the reply! I'm not familiar with "alias method" but from what I just read, doesn't it work in opposite direction? That is, if I have a segment it can generate some position?  
> **username_1**: One interpretation of the alias method is that it scales and reorders the segments so that the segment containing a particular value $x$ can be determined in two steps: rounding $x$ to an integer, and then comparing the fractional part of $x$ against at most one segment boundary that lies between that integer and the next. So then you can generate a random segment by generating a random $x$ and applying this test.  
> **username_2**: It depends on your computational model. Suppose for example that the pieces have sizes $1/2,1/4,1/8,\ldots,1/2^n,1/2^n$ ($n$ pieces in total). Can you solve your problem in your case in $O(1)$?  
> **username_2**: The alias method can generate a random segment from the rod in proportion to its length. As username_1 mentions, to that end it cuts the large segments (those larger than $1/n$) into pieces and reorders them; the pieces are not contiguous. In the end, each part of length $1/n$ will consist of a piece of a large segment, and possibly a small segment.  
> **username_3**: How do you find this approach:  
> **username_3**: What if you first pre-process the cut positions in such a way, that you can get the desired answer by reading the input bit-by-bit? In your example, you read 8 and this gives 3rd piece. If the input would be 7.852, the algorithm would in first three steps return the position 2-3 and in the next step (after reading digit 2) the answer would be 2.  

---

## 0 answers

