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

Листинг 2.5. 
Gene.java (продолжение)
public boolean
linearContains(Codon key) {
for
(Codon codon : codons) {
if
(codon.compareTo(key) == 0) {
return true
; // поиск совпадений
}
}
return false
;
}
public static void
main(String[] args) {
String geneStr = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGA
CTCCCTTT";
Gene myGene = 
new
Gene(geneStr);
Codon acg = 
new
Codon("ACG");
Codon gat = 
new
Codon("GAT");
System.
out
.println(myGene.linearContains(acg)); // true
System.
out
.println(myGene.linearContains(gat)); // false
}
}
ПРИМЕЧАНИЕ
Эта.функция.имеет.демонстрационное.назначение..Все.классы.стандартной.библио-
теки. Java,. реализующие. интерфейс. Collection. (например,. ArrayList. и. LinkedList),.
содержат.метод.contains(),.который,.вероятно,.будет.реализован.лучше,.чем.все,.что.
мы.пишем.
2.1.3. Бинарный поиск
Существует.более.быстрый.способ.поиска,.чем.просмотр.всех.элементов..Но.
при.этом.требуется.заранее.знать.кое-что.о.последовательности.структуры.
данных..Если.известно,.что.структура.отсортирована.и.мы.можем.мгновенно.
получить.доступ.к.любому.ее.элементу.по.его.индексу,.то.можно.выполнить.
бинарный.поиск.
При.бинарном.поиске.средний.элемент.в.отсортированном.диапазоне.элементов.
проверяется.и.сравнивается.с.искомым.элементом..По.результатам.сравнения.
диапазон.поиска.уменьшается.наполовину,.после.чего.процесс.повторяется..Рас-
смотрим.его.на.конкретном.примере.
Предположим,.что.у.нас.есть.список.отсортированных.по.алфавиту.слов.(
cat
.
(кошка),.
dog
.(собака),.
kangaroo
.(кенгуру),.
llama
.(лама),.
rabbit
.(кролик),.
rat
.
(крыса),.
zebra
.(зебра)).и.мы.ищем.слово.
rat
.(крыса).

---

2.1. Поиск ДНК
53
1.. Мы.определили,.что.средний.элемент.в.списке.из.семи.слов.—.это.
llama
.(лама).
2.. Теперь.можем.определить,.что.по.алфавиту.
rat
.(крыса).идет.после.
llama
.
(лама),.поэтому.она.должна.находиться.(это.неточно).в.той.половине.списка,.
которая.идет.после.
llama
.(лама)..(Если.бы.мы.нашли.
rat
.(крыса).на.этом.шаге,.
то.могли.бы.вернуть.местонахождение.этого.слова;.если.бы.обнаружили,.что.
искомое.слово.стоит.перед.средним.словом,.которое.мы.проверяли,.то.могли.
бы.быть.уверены,.что.оно.находится.в.половине.списка.до.
llama
.(лама).)
3.. Мы.могли.бы.повторить.пункты.1.и.2.для.той.половины.списка,.в.которой,.
как.уже.знаем,.вероятно,.находится.слово.
rat
.(крыса)..По.сути,.эта.половина.
становится.новым.исходным.списком..Указанные.пункты.выполняются.по-
вторно.до.тех.пор,.пока.
rat
.(крыса).не.будет.найдена.или.же.диапазон,.в.ко-
тором.выполняется.поиск,.больше.не.будет.содержать.элементов.для.поиска,.
то.есть.слова.
rat
.(крыса).не.будет.существовать.в.заданном.списке.слов.
Процедура.бинарного.поиска.проиллюстрирована.на.рис..2.3..Обратите.внимание.
на.то,.что,.в.отличие.от.линейного.поиска,.здесь.не.подразумевается.проверка.
каждого.элемента.
. .