21.4. Поиск
После сортировки информация приводится к виду, который удобен для поиска нужной информации. Так, при поиске телефонного номера проще всего бегло просмотреть страницы телефонной книги, пока не будет приблизительно найдено место, где должен располагаться искомый номер. Именно этот раздел книги необходимо просмотреть подробнее. И большинство из нас так поступают автоматически.
Если вы хотите воспроизвести этот процесс в рамках PHP-сценария, необходимо позаботиться обо всех шагах. Самым простым способом является начать с начала книги и просматривать каждую запись до тех пор, пока не будет обнаружена искомая запись. И если после выполнения этих действий ничего не найдено, значит, искомая запись не существует. Пожалуй, не надо специально напоминать, что это наихудший метод поиска, но зачастую это единственное, что у нас есть в распоряжении. Если данные не отсортированы, лучшего способа не существует.
Поиск можно значительно усовершенствовать, если прибегнуть к двоичному поиску. При этом требуется, чтобы данные были отсортированы. К счастью, мы уже убедились в том, что это относительно несложно сделать. Двоичный поиск подразумевает поочередное разбиение списка на части, одна из которых не должна содержать искомой информации, а другая - должна. Двоичный поиск следует начинать с середины списка. Если элемент, расположенный посередине, предшествует искомому элементу, можно быть полностью уверенным в том, что искомый элемент располагается после среднего элемента. Теперь нам следует искать только среди половины из всех элементов. Повторяя эти шаги, мы очень быстро найдем искомый элемент. В худшем случае потребуется просмотреть log n элементов просматриваемого списка. Если имеется 128 элементов, для поиска значения потребуется сделать 7 попыток (листинг 21.6).
Листинг 21.6. Двоичный поиск
<?php
// byName
// сравнить служащих по их именам function byName($left, $right)
{
return(strcmp($left[0], $right[0]));
}
// Создать список служащих ( имя, должность, ставка) $employee = array(
array("Mckillop, Jeff", "Executive", 50),
array("Porter, Carl", "Instructor", 45),
array("Marazzani, Rick", "Manager", 35),
array("Dibetta, Bob", "Programmer", 65),
array("Atkinson, Leon", "President", 100)); // отсортировать список usort($employee, "byName"); print("<pre>"); print_r($employee); print("</pre>n"); // Задать искомую запись $Name = "Porter, Carl"; print("Searching for $Name<br>n"); // Задать диапазон поиска $lower_limit = 0;
$upper_limit = count($employee) - 1; //Выбрать середину списка
$index = floor(($lower_limit + $upper_limit)/2); while($lower_limit < $upper_limit)
{
if(strcmp($employee[$index][0], $Name) < 0)
// Выбрать первую половину $lower_limit = $index + 1;
elseif(strcmp($employee[$index][0], $Name) > 0)
// Выбрать вторую половину $upper_limit = $index - 1;
else
//Искомая запись найдена $lower_limit = $index; $upper_limit = $index;
} 
//Выбрать среднюю точку
$index = floor(($lower_limit + $upper_limit)/2);
}
// Распечатать результаты print("Position $index<br>n"); print("{$employee[$index][0]}
{$employee[$index][1]}<br>n");
?>

21.5. Индексирование
Сортировка данных требует определенных временных затрат, но она позволит сэкономить время при последующих операциях поиска. Но на выполнение операции поиска тоже требуется определенное время. Двоичный поиск позволяет ускорить и этот процесс. Когда требуется выполнить сотни операций поиска, может потребоваться усовершенствовать и этот процесс, и здесь поможет создание индекса. Для того чтобы поиск выполнялся достаточно быстро, необходимо провести большую предварительную работу.
Посмотрим, как можно ускорить двоичный поиск из листинга 21.6. Для этого потребуется массив, который при заданном имени возвращает его положение в исходном массиве и позволит, таким образом, создать список соответствий. Обратите внимание на программный код, приведенный в листинге 21.7. Не будем думать о сортировке списка, поскольку это нам не поможет, так как мы собираемся просматривать каждый элемент массива.
По мере просмотра элементов массива создается новый массив. Индекс массива содержит имена служащих компании. Каждый элемент индекса является массивом индексов массива employee. После того как индекс создан, для поиска служащего будет достаточно одного-единственного оператора. По найденному имени в массиве можно найти значения индексов для массива employee.

| Листинг 21.7. Создание индекса_
<?php
// Создать список служащих ( имя, должность, ставка) $employee = array(
array("Mckillop, Jeff", "Executive", 50),
array("Porter, Carl", "Instructor", 45),
array("Marazzani, Rick", "Manager", 35),
array("Dibetta, Bob", "Programmer", 65),
array("Atkinson, Leon", "President", 100)); // создать индекс $employeeIndex = array(); foreach($employee as $id=>$val)
{
$employeeIndex[$val[0]] = $id;
}
//где Карл?
$index = $employeeIndex["Porter, Carl"]; print("Position $index<br>n");
print("{$employee[$index][0]} {$employee[$index][1]}<br>n");
?> 
Этот пример не совсем реалистичен, так как мы выполняем только одну операцию поиска и при каждом запросе потребуется создание индекса. А индекс достаточно создать только один раз, поскольку массив employee не претерпевает изменений. Возможно, пользуясь возможностью трансформации, которую имеет PHP, этот массив можно сохранить в отдельном файле, который можно по необходимости загрузить. Аналогичный программный код был написан автором для индексирования ключевых слов, которые возникают на Web-узле, в ходе выполнения проекта FreeTrade.
Конечно, для обработки данных мощные решения предлагают базы данных. В большинстве случаев хранение больших объемов данных лучше всего возложить на базы данных, поскольку они имеют специальные возможности для поиска и сортировки. Базы данных описываются в главе 23, "Интеграция баз данных".