Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Рис. 2.3.
В худшем случае при бинарном 
поиске придется просматривать только 
lg(n) элементов списка
При.бинарном.поиске.пространство.поиска.постоянно.сокращается.вдвое,.по-
этому.в.худшем.случае.время.выполнения.поиска.составляет.
O
(lg.
n
)..Однако.
здесь.есть.своеобразная.ловушка..В.отличие.от.линейного.поиска,.для.бинарного.
требуется.отсортированная.структура.данных,.а.сортировка.требует.времени..
На.самом.деле.сортировка.занимает.время.
O
(
n
.lg.
n
).даже.при.использовании.
лучших.алгоритмов..Если.мы.собираемся.запустить.поиск.только.один.раз,.
а.исходная.структура.данных.не.отсортирована,.возможно,.имеет.смысл.просто.
выполнить.линейный.поиск..Но.если.поиск.должен.выполняться.много.раз,.то.
стоит.потратить.время.на.сортировку,.чтобы.каждый.отдельный.поиск.занял.
значительно.меньше.времени.
Написание.функции.бинарного.поиска.для.гена.и.кодона.мало.отличается.от.
написания.функции.для.любого.другого.типа.данных,.поскольку.объекты.типа.
Codon
.можно.сравнивать.между.собой,.а.тип.
Gene
.—.это.просто.список.
ArrayList
.
(листинг.2.6)..Обратите.внимание.на.то,.что.в.следующем.примере.мы.в.пер-
вую.очередь.выполняем.сортировку.кодонов..Это.устраняет.все.преимущества.
выполнения.бинарного.поиска,.так.как.сортировка.займет.больше.времени,.

---

54
Глава 2.
Задачи поиска
чем.поиск..Однако.в.демонстрационных.целях.она.необходима,.поскольку.при.
запуске.данного.примера.мы.не.можем.знать,.что.кодоны.в.списке.
ArrayList
.
отсортированы.
Листинг 2.6. 
Gene.java (продолжение)
public boolean
binaryContains(Codon key) {
// бинарный поиск работает только с отсортированными коллекциями
ArrayList sortedCodons =