38
правок
Изменения
Нет описания правки
== Алгоритм правостороннего/левостороннего поиска ==
[[Файл:cheme.jpg]]<br>
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1, или же пока мы не найдём искомый индекс. == Код == l := 0; // l - левая граница r := n + 1; // r - правая граница while (l < r - 1) // запускаем цикл begin m := (l + r) div 2; // m - середина области поиска if (a[m] < k) then l := m else r := m; // сужение границ end; if (a[r] = k) then result := r // выводим найденный индекс else result := -1; // если элемент не найден возвращаем -1 В случае правостороннего поиска изменится знак сравнения при сужении границ на (a[m] <= k), также при выводе найденного индекса, мы сравниваем искомый элемент k с a[l].
