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

56
Глава 2.
Задачи поиска
ПРИМЕЧАНИЕ
В.листинге.2.8.задействовано.много.импортированных.типов..В.этой.главе.мы.еще.раз.
воспользуемся.файлом.GenericSearch.java.для.многих.дополнительных.универсальных.
алгоритмов.поиска,.что.избавит.нас.от.необходимости.импорта.
Листинг 2.8. 
GenericSearch.java
package
chapter2;
import
java.util.ArrayList;
import
java.util.HashMap;
import
java.util.HashSet;
import
java.util.LinkedList;
import
java.util.List;
import
java.util.Map;
import
java.util.PriorityQueue;
import
java.util.Queue;
import
java.util.Set;
import
java.util.Stack;
import
java.util.function.Function;
import
java.util.function.Predicate;
import
java.util.function.ToDoubleFunction;
public class
GenericSearch {
public static
extends
Comparable> 
boolean
linearContains(List 
list, T key) {
for
(T item : list) {
if
(item.compareTo(key) == 0) {
return true
; // поиск совпадений
}
}
return false
;
} 
// предполагается, что *список* уже отсортирован
public static
extends
Comparable> 
boolean
binaryContains(List 
list, T key) {
int
low = 0;
int
high = list.size() — 1;
while
(low <= high) { // пока еще есть место для поиска
int
middle = (low + high) / 2;
int
comparison = list.get(middle).compareTo(key);
if
(comparison < 0) { // средний кодон меньше искомого
low = middle + 1;
} 
else if
(comparison > 0) { // средний кодон больше искомого
high = middle — 1;
} 
else
{ // средний кодон равен искомому
return true
;
}
}
return false
;

---

2.2. Прохождение лабиринта
57
}
public static void
main(String[] args) {
System.
out
.println(
linearContains
(List.
of
(1, 5, 15, 15, 15, 15, 20), 
5)); // true
System.
out
.println(
binaryContains
(List.
of
("a", "d", "e", "f", "z"), 
"f")); // true
System.
out
.println(
binaryContains
(List.
of
("john", "mark", "ronald", 
"sarah"), "sheila")); // false
}
}
ПРИМЕЧАНИЕ
Ключевое.слово.extends.в.коде.T.extends.Comparable.означает,.что.T.должен.быть.
типом,.реализующим.интерфейс.Comparable.
Теперь.вы.можете.попробовать.выполнить.поиск.для.других.типов.данных..Эти.
методы.можно.использовать.практически.для.любой.коллекции.Java..В.этом.
преимущество.общего.написания.кода.
2.2. ПРОХОЖДЕНИЕ ЛАБИРИНТА
Поиск.пути.через.лабиринт.аналогичен.многим.распространенным.задачам.поиска.
в.информатике..Почему.бы.буквально.не.найти.путь.через.лабиринт,.чтобы.про-
иллюстрировать.алгоритмы.поиска.в.ширину,.поиска.в.глубину.и.алгоритмы.A*?
Наш.лабиринт.представляет.собой.двумерную.сеть.ячеек.—.объектов.
Cell
.(ли-
стинг.2.9)..
Cell
.—.это.перечисление.значений.
String
,.где.
"
.
"
.означает.пустое.
пространство,.а.
"X"
.—.занятое..В.иллюстративных.целях.при.выводе.лабиринта.
на.печать.существуют.и.другие.варианты.заполнения.ячеек.