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 не меняется?
что-то забыто, в общем.
с этим я согласна