Поиск числа в массиве за наименьшее время - PullRequest
3 голосов
/ 23 апреля 2010

Элементы массива расположены в неубывающем порядке.Мне нужно найти в массиве заданный элемент за минимально возможное время.

Ответы [ 4 ]

2 голосов
/ 23 апреля 2010

Поскольку массив отсортирован, вы можете использовать Binary Search .

Поиск linear займет O(n) времени, поскольку не использует отсортированное свойство. Но поиск binary займет O(log n) время.

2 голосов
/ 23 апреля 2010

Используйте двоичный поиск , чтобы найти его.

0 голосов
/ 23 апреля 2010

Что ж, если вам нужно лучше, чем Binary, вы можете использовать эвристику, такую ​​как поиск Ньютона, которая является производной от двоичного поиска, с перемещением границы разделения - каждый раз, когда значение больше, увеличивайте шаг, если он меньше, уменьшить его.

split = 0.5;
while(1)
{
    point = lower+split*(upper-lower);
    if(x>a[point])
    {
        lower = point;
        split*= 1.2
    }
    else if(x<a[point])

    {
        upper=point;
        split /=1.2
    } else break;
}

Это предположительно дает лучшие результаты с наборами, которые имеют полиномиальные разметки и несвязанные множества. Это дает худшие результаты со случайными или линейными раскладками. Это также может привести к сбою с ростом сплита выше 1 без надлежащих мер безопасности.

0 голосов
/ 23 апреля 2010

Если все, что вы знаете, это то, что массив отсортирован в неубывающем порядке, вы не можете сделать лучше, чем бинарный поиск с гарантированной производительностью O(log N) (как указано другими авторами).

Если вы можете предположить достаточно равномерное распределение чисел в массиве, то интерполяционный поиск может дать O(log log N) производительность в среднем случае, что лучше, чем двоичный поиск. (Однако в худшем случае - массив с экспоненциальным ростом - это O(N)).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...