Given an array of size N, there exist a pattern such that, a[i]-M <= a[i+1] <= a[i]+M . Suggest an algorithm to search for a number in the given array. The solution should be better than O(n).
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 12:47:26 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Are you sure it's supposed to be better than O(n) even when the array would be full of repeated 4 and 2 (I mean, 4 2 4 2 4 2 4 2 .....) and in the middle would be 3 and you had to find it?
Sorry without repetition.Please tell your approach?
I was just asking a question to make sure the algorithm is supposed to be better than O(n) even in the absolute worst case.
M is an input to the program, right? And are there any other constraints on Array?
what do you mean without repetition? do you mean that the numbers are distinct?
yes.Please tell the approach
if M is small, suppose we want to find b: so we start from the first element, if the element is b, we are done. else we will jump |(a[cur]-b)/M|+1 steps. this is because we know anything in between would not be able to be equals to b. Repeat until we find b.
The time complexity of the algorithm is proportional to the number of jumps. And we know that at worst case we can only have 2*M jumps of length 1, 2*M jumps of length 2 and so on till 2*M jumps of length x.
So we have 2M(1+2+...+x) = N-1 as the sum of the jumps can be as most N-1. So (x+1)x = (N-1)/M, and x is about sqrt((N-1)/M), so the number of jumps is 2M*sqrt((N-1)/M) = 2*sqrt((N-1)M)
So the time complexity is O(sqrt(N*M)), it is better than O(N) if M is < N, and if M is greater than N, the complexity is O(N) as there is still at most N jump.
Maybe i misunderstood the problem, but how can we do it faster than reading array? If it is problem with Q queries, why can't we just memorize position of each value, i.e. will make map, where m[i] — position of number i and answer in O(logN) for each query. If it is correct it can be done in O((N + Q)logN) or in O(NlogN + Q). But if this task is interactive i don't know what to do.
usually in this kind of situation, the array will be given, so can you consider the time complexity without reading the array.