Jump Search псевдокод из учебника по Алгоритмам и Структурам данных

я думаю, что алгоритм в учебнике реализован не верно, что думаете вы?
https://en.wikipedia.org/wiki/Jump_search
:-)

выше я привела ссылку на алгоритм из Вики.
вот что пишет автор учебника:
автор учебникаWhen we have an already sorted list, then the other efficient algorithm to search for a value is jump
search or block search. In jump search, it is not necessary to scan all the elements in the list to
find the desired value. We just check an element and if it is less than the desired value, then some
of the elements following it are skipped by jumping ahead. After moving a little forward again,
the element is checked. If the checked element is greater than the desired value, then we have
a boundary and we are sure that the desired value lies between the previously checked element
and the currently checked element. However, if the checked element is less than the value being
searched for, then we again make a small jump and repeat the process.

Once the boundary of the value is determined, a linear search is done to find the value and its
position in the array.

For example, consider an array a[] = {1,2,3,4,5,6,7,8,9} . The length of the
array is 9. If we have to find value 8 then following steps are performed using the jump search
technique.

Step 1: First three elements are checked. Since 3 is smaller than 8, we will have to make a
jump ahead

Step 2: Next three elements are checked. Since 6 is smaller than 8, we will have to make a
jump ahead

Step 3: Next three elements are checked. Since 9 is greater than 8, the desired value lies
within the current boundary

Step 4: A linear search is now done to find the value in the array.

имхо, автор забыл, что нужно "прыгать"

у меня наблюдение: к концу книги становится все больше и больше опечаток
(т.е. получается, что до конца дочитывают немногие)

Leonid Kudryavtsev,

в том-то и дело, что нет: прыжок происходит только один раз в sqrt(n).
по идее прыжки в первом цикле должны происходить пока мы не наийдем нужное значение или число большее, чем искомое.

Вот что происходит в алгоритме из учебника

*) рассмотрим массив a[] = {0,1,2,3,4,5,6,7,8,9} и пусть искомое число будет 8 (как в примере)
*) low = 0; high = 8; step = 3; i = 0
*) Jump Loop:
1)
i = 0 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 3 + 1 = 4
i = i + 1 = 0 + 1 = 1

2)
i = 1 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 4
i = i + 1 = 0 + 1 = 2

3)
i = 2 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 4
i = i + 1 = 0 + 1 = 3

4)
i = 3 < step = 3 -> False -> we exit the loop
low = 3
и дальше мы с помощью линейного поиска проверяем все позиции от arr[3] до arr[9] в поисках нужного знчения
это неверно, и это не то, что должен делать JumpSearch, обратите внимание на количество операций нужное для реализации алгоритма (их 10, т.е фактически это не лучше, чем линейный поиск!)

в вики, например, все происходите следующим образом (и это правильно):

и прыжки длиной в sqrt(n) происходят до тех пор, пока val не станет больше или равно arr[high] или пока low не станет больше чем n.

exp98,
в книге только псевдокод. и свой код нужно писать по псевдокоду.
(у меня нет проблем с написанием кода по псевдокоду, проблема в том, что я думаю, что псевдокод не верен)

mayton,
тут модульный тест не поможет :)
т.к. даже "неправильный" алгоритм найдет число в массиве (если оно там есть), и не найдет, если его там нет.

некорректность алгоритма можно доказать
а) методом подсчета шагов цикла (это можно сделать прямо в псевдокоде)
б) сравнив ран-тайм "верного" алгоритма с ран-таймом алгоритма из книги
(например, мы можем принять алгоритм из вики за "верный")

ну exp98,
в данном случае это необходимо, потому что речь идет о корректности/некорректности логики решения
(сначала планируем - потом пишем) :-)

mayton,
вопрос адресован в первую очередь к тем кто может понять псевдокод и сравнить с кодом приведенным в Вики

Имя пользователя1,

да обыкновенно, беру книгу и читаю, а если что-то непонятно, спрашиваю на sql.ru

Имя пользователя1тут какая-то непонятная хрень.
зачем 3 шаг повторять, если переменная STEP не меняется?
что-то забыто, в общем.
с этим я согласна

существует всего 4 основных алгоритма поиска:
1) линейный поиск
2) двоичный поиск
3) поиск методом интерполяции
4) прыжковый (пошаговый) поиск (Jump Search)

у меня проблема возникла только с методом 4

mayton,

хэш поиск = поиск по хэш ключу + линейный поиск
поиск по хэш ключу будет проведен по одному из 4х методов

Есть фраза "пока val не станет".
Разве val не константа?
Если val < arr[high] затем мы прибавляем low = high + 1; ....
а) подразумевается убывающее упорядочивание.
б) А где обрабатывается случай val == arr[high] ?[/quot]

1) полный алгоритм вики можно найти по ссылке https://en.wikipedia.org/wiki/Jump_search
там все случаи обрабатываются
2) я привела только часть с прыжками, потому что именно она неправильно реализована в книге
3) по поводу констант, если быть точным, то нужно выполнение условия val = arr[high]

mayton,
я говорю конкретно об алгоритмах поиска , а не о всех возможных алгоритмах
есть алгоритмы поиска (и их 4), а есть структуры данных, это не одно и тоже
не существует метода хэш-поиск, но зато существует структура данных - хэш таблица,
которая позволяет быстрый поиск данных по ключу. структуры данных как раз и
создаются для того, чтобы получить лучшие результаты, чем позволяют стандартные алгоритмы

mayton,
с алгоритмом из вики проблем нет, там все норм.
проблема с алгоритмом в самом первом посте: там все будет находится правильно, но по скорости выполнения он будет не лучше, чем линейный поиск

exp98,

поправка
3) по поводу констант, если быть точным, прыжки должны совершатся до тех пор пока val >= arr[high]

скорость поиска для JumpSearch O(sqrt(n)), это лучше, чем линейный поиск O(n)

при условии, что данные распределены равномерно, интерполяционный поиск будет эффективнее, чем двоичный

да, согласилась

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

напомню, мы говорим, о поиске конкретного элемента в конечномерном массиве
так что не наговаривай на автора
тут нет ни континума, ни псевдоконтинума. и вероятностных методов тоже.

Тема о том, что в псевдокоде, приведенном в посте номер 1, Jump Search алгоритм реализован неверно

Имя пользователя1,
для строк интерполяционный поиск в лоб применить нельзя, но можно сделать, что-то типа
aaa, aab, aba, abb

и я думаю, что на практике нечто подобное и применяется