Валерий Лаптев писал(а):
Все согласованно изменено.
Да, спасибо. С этим моментом разобрался. Суть в том, что в этом варианте поиска, как и написано в книге, "ищется не элемент a[m] = х, а граница, отделяющая все элементы, меньшие х, от всех прочих". Тогда для частного случая, когда элемента x в массиве нет, т.е. x превосходит все a[i], действительно необходимо проверить в цикле и последний элемент с индексом N - 1, поэтом R изначально должно быть N. В ином случае этот последний элемент проверен не будет и последующее утверждение, что в случае, "если R = N, то искомого значения в массиве нет" будет неверным.
В конечном итоге полностью вариант из учебника должен выглядит как-то так:
Код:
L := 0; R := N;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1 ELSE R := m END
END;
IF R = N THEN
(* Если R = N, то искомого значения в массиве нет. *)
(* элемент найден *)
ELSE
(* В противном случае нужно учесть, что элемент a[R] еще не сравнивался. *)
IF a[R] = х THEN
(* элемент найден *)
ELSE
(* элемент не найден *)
END
END
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1 ELSE R := m END
END;
IF R = N THEN
(* Если R = N, то искомого значения в массиве нет. *)
(* элемент найден *)
ELSE
(* В противном случае нужно учесть, что элемент a[R] еще не сравнивался. *)
IF a[R] = х THEN
(* элемент найден *)
ELSE
(* элемент не найден *)
END
END
Так вот, глядя на такой код, мне в голове "лезет" немного другой вариант:
Код:
L := 0; R := N - 1;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1 ELSE R := m END
END;
IF a[R] = х THEN
(* элемент найден *)
ELSE
(* элемент не найден *)
END
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1 ELSE R := m END
END;
IF a[R] = х THEN
(* элемент найден *)
ELSE
(* элемент не найден *)
END
Здесь a[R] сравнивается по окончании цикла в любом случае, так как частный случай с отсутствием искомого значение в массиве надо учесть. По сути проверка последнего элемента в этом частном случае перенесена из цикла в условный оператор. Сам условный оператор получается "проще" и R тут уже будет достаточно N - 1, но теряется ... эммм... концептуальная простота что-ли
алгоритма, т.к. простое словесное описание действий, выполняемых в цикле, данное ранее ("ищется не элемент a[m] = х, а граница, отделяющая все элементы, меньшие х, от всех прочих") здесь уже не работает - в обсуждаемом частном случае до границы мы так и не дойдём. Кроме того, теряется и "фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R", на котором чуть раньше заостряет внимание автор.