Hi guys,
Can anyone share their ideas over searching over a non-monotonic range. Is there a way that the basic binary search implementation can be modified to handle non-monotonic ranges?
Please assist with your ideas and thought/techniques.
Thank you
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
In general you cannot deal with non-monotonic chunks of data faster than O(n) because you have to look at all N elements to be sure whether an element is presented or not, because you have absolutely no extra information. Even if you've checked N-1 elements, you know nothing about the remaining Nth.
Thank you International Grandmaster Yeputons. But what if we have additional information that the data set is monotonic over some ranges. Let me illustrate
[a..b] is the full range and is not monotonic a < x,y < b [x..y] is monotonic
So i guess what am asking is that when we have monotonic ranges inside a bigger non-monotonic range and we have perfect information of the indexes, Can we intelligently search for data ?
Binsearch over each interval which may contain needle is resonable for you?
You can run a binary search on the monotonic piece, and if it fails, a linear search on what's left. Depending on the details of your problem, this may or may not result in a speedup.