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

new
ArrayList<>(codons);
Collections.
sort
(sortedCodons);
int
low = 0;
int
high = sortedCodons.size() — 1;
while
(low <= high) { // while there is still a search space
int
middle = (low + high) / 2;
int
comparison = codons.get(middle).compareTo(key);
if
(comparison < 0) { // средний кодон меньше искомого
low = middle + 1;
} 
else if
(comparison > 0) { // средний кодон больше искомого
high = middle — 1;
} 
else
{ // средний кодон равен искомому
return true
;
}
}
return false
;
}
Рассмотрим.выполнение.этой.функции.построчно:
int
low = 0;
int
high = sortedCodons.size() — 1;
Начнем.поиск.с.диапазона,.который.охватывает.весь.список.(ген):
while
(low <= high) {
Мы.продолжаем.поиск.до.тех.пор,.пока.существует.диапазон.для.поиска..Когда.
low
.станет.больше,.чем.
high
,.это.будет.означать,.что.в.списке.не.осталось.фраг-
ментов.для.просмотра:
int
middle = (low + high) / 2;
Вычисляем.среднее.значение.
middle
,.используя.целочисленное.деление.и.простую.
формулу.вычисления.среднего,.знакомую.еще.по.начальной.школе:
int
comparison = codons.get(middle).compareTo(key);
if
(comparison < 0) { // средний кодон меньше искомого
low = middle + 1;
Если.искомый.элемент.находится.после.среднего.элемента.текущего.диапазона,.
то.изменяем.диапазон,.который.будем.рассматривать.на.следующей.итерации.

---

2.1. Поиск ДНК
55
цикла,.перемещая.
low
.на.следующий.после.текущего.среднего.элемента..Именно.
на.этом.шаге.мы.вдвое.сокращаем.диапазон.поиска.для.следующей.итерации:
} 
else if
(comparison > 0) { // средний кодон больше искомого
high = middle — 1;
Если.искомый.элемент.меньше,.чем.средний,.мы.точно.так.же.делим.диапазон.
пополам.и.выбираем.другое.направление: