Поиск в строке делением пополам (у Вирта ошибка?)

[GrishinUS]

Добрый день,

в книге Н. Вирта "Алгоритмы и Структуры данных" нашел вот такой код :

T : ARRAY [0..N-1] OF String;
x : String;
....
L := 0; R := N;
WHILE L < N DO BEGIN
    m := (L + R) div 2; i := 0;
    WHILE (T[m, i] = x[i]) and (CHR(x[i]) <> #0) DO i := i + 1;
    IF T[m, i] < x[i] THEN L := m + 1 ELSE R := m;
END;
IF R < N THEN BEGIN
    i := 0;
    WHILE (T[R, i] = x[i]) and (x[i] <> #0) DO i := i + 1;
END;
(* (R < N) and  (T[R, i] = x[i]) фиксирует совпадение *)

Не могу понять с какой целью R присваивается значение N, если массив определен как

T : ARRAY [0..N-1] OF String;

Если положить

R := N - 1;

то программа будет работать в общем случае не хуже, а в лучшем случае на короче 1 проход цикла.
Или я что-то упустил?

[worm2]

Посмотрите внимательно, что будет в этом случае, если N=2, например. В этом случае до элемента с индексом 1 никогда дело не дойдёт (оператор div округляет в сторону нуля).

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

[GrishinUS]

Цитата:

Посмотрите внимательно, что будет в этом случае, если N=2, например. В этом случае до элемента с индексом 1 никогда дело не дойдёт (оператор div округляет в сторону нуля).

Да, все правильно, спасибо.

Цитата:

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

тогда что насчет поиска Кнута-Морриса-Пратта?