метод равномерного и дихотомического поиска Опции

[Catty]

Нигде не могу в сети найти алгоритмы этих методов, если у кого то есть алгоритмы киньте сюда пожалуйста или дайте ссылку! :flowers: :flowers:

[klem4]

2.3. Дихотомический (бинарный) поиск
Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.

Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.

На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

Запишем все сказанное в виде программы:

l := 1; r := n;
while (l<>r) do
begin
  m := (l+r) div 2;
  if Key>A[m] then l := m+1 else r := m;
end;
if A[l]=Key then <элемент найден> else <элемент не найден>;
Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).

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

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

i := n;
while (i>=1)and(A[i]>Key) do
begin
  A[i+1] := A[i]; {сдвигаем}
  Dec(i);
end;
A[i+1] := Key;
Inc(n);
Такая операция добавления имеет сложность T(n).

Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.