Programming Taskbook 0

Специальный поиск 
Методы array of T
 
BinarySearch(x: T): integer 
AdjacentFind([pred:
(T,
T)
->
boolean;] [start:
integer]):
integer 
Метод BinarySearch позволяет выполнять очень эффективный поиск в 
массиве, отсортированном по возрастанию. По сравнению с «обычными» 

---

Глава 5. Дополнительные средства обработки массивов 
107 
методами поиска он имеет две особенности. Во-первых, при наличии не-
скольких элементов с требуемым значением (разумеется, все такие элемен-
ты в отсортированном массиве располагаются подряд) он возвращает ин-
декс какого-либо из этих элементов, не обязательно первого или последне-
го. Во вторых, если требуемое значение в массиве не найдено, метод Bina-
rySearch возвращает не особое значение –1, а некоторое отрицательное 
число, определяющее позицию, в которую можно было бы добавить тре-
буемое значение с сохранением упорядоченности элементов массива. Бо-
лее точно, если возвращено отрицательное число –k, то это означает, что 
требуемое значение (при его наличии) должно было бы располагаться пе-
ред элементом с индексом k – 1. Примеры: 
var
a:=
Arr(11,
22,
33,
33,
44,
44,
44,
44,
44,
55,
55,
55,
55,
66); 
Println(a.BinarySearch(33)); // 2 
Println(a.BinarySearch(44)); // 6 
Println(a.BinarySearch(55)); // 10 
Println(a.BinarySearch(0)); // -1 
Println(a.BinarySearch(40)); // -5 
Println(a.BinarySearch(50)); // -10 
Println(a.BinarySearch(80)); // -15 
Варианты метода AdjacentFind позволяют искать пары соседних эле-
ментов, удовлетворяющие предикату pred, и возвращают индекс левого 
элемента первой найденной пары. В первый параметр предиката подстав-
ляется левый элемент каждой пары, а во второй — правый элемент. Если 
предикат pred не указан, то ищутся пары совпадающих элементов (иными 
словами, в данном случае используется предикат вида (e1, e2) -> e1 = e2). 
Если указан параметр start, то поиск начинается с пары, левый элемент ко-
торой имеет индекс start; если параметр start отсутствует, то он считается 
равным 0. Если в массиве отсутствуют пары, удовлетворяющие требуемо-
му условию, то метод возвращает значение –1. Примеры: 
var a := Arr(11, 22, 33, 33, 44, 44, 66, 55, 15); 
Println(a.AdjacentFind); // 2 
Println(a.AdjacentFind(3)); // 4 
Println(a.AdjacentFind((e1, e2) -> (e1 + e2) mod 10 = 0)); // 5 
Println(a.AdjacentFind((e1, e2) -> e1 > e2)); // 6 
Println(a.AdjacentFind((e1, e2) -> e1 = -e2)); // -1 
В отношении скорости выполнения метод AdjacentFind эквивалентен 
соответствующему циклу по переменной i, в котором анализируются эле-
менты массива с индексами i и i + 1. 
Для иллюстрации применения некоторых из описанных методов обра-
тимся к задачам из группы Array. 

---

108 
В задаче Array47 требуется найти количество различных элементов в 
исходном целочисленном массиве.
Если использовать только средства традиционного Паскаля и не при-
менять дополнительные структуры данных, то решение можно предста-
вить в следующем виде: 
Task('Array47'); // Вариант 1 
var a := ReadArrInteger; 
var k := 1; 
for var i := 1 to a.Length - 1 do 
begin 
var p := 1; 
for var j := i - 1 downto 0 do 
if a[j] = a[i] then 
begin 
p := 0; 
break; 
end; 
k += p; 
end; 
Write(k); 
Мы сразу, до цикла, записываем в счетчик k значение 1, чтобы учесть 
первый элемент массива. Остальные элементы анализируются в цикле; 
счетчик увеличивается только если значение очередного элемента a[i] ранее 
в массиве не встречалось. Для поиска значения a[i] в предыдущей части 
массива приходится организовывать вложенный цикл по переменной j. Ре-
зультатом поиска является переменная p, равная 1, если элемент a[i] ранее в 
массиве не встречался, и равная 0 в противном случае. Полученное значе-
ние переменной p можно без дополнительной проверки добавить к счетчи-
ку. 
С применением одного из методов поиска алгоритм можно суще-
ственно сократить: 
Task('Array47'); // Вариант 2 
var a := ReadArrInteger; 
var k := 1; 
for var i := 1 to a.Length - 1 do 
if a.LastIndexOf(a[i], i - 1) = -1 then 
k += 1; 
Write(k); 
Еще более коротко можно записать условие, используя операцию in и 
выражение для среза массива: 
Task('Array47'); // Вариант 3 

---