Базы данных существуют для того, чтобы время от времени пользователи могли найти нужную запись, введя ее ключ. Существует один метод поиска информации в неупорядоченном массиве, и другой для поиска в упорядоченном массиве. В набор стандартной библиотеки компиляторов языка С входит стандартная функция bsearch(). Тем не менее, как и в случае сортировки, процедуры общего назначения иногда совсем не эффективны при использовании в критических ситуациях из-за накладных расходов, связанных с их обобщением. Кроме того, функцию bsearch() невозможно применить к неупорядоченным данным.
Методы поиска
Для нахождения информации в неупорядоченном массиве требуется последовательный поиск, начинающийся с первого элемента и заканчивающийся при обнаружении подходящих данных либо при достижении конца массива. Этот метод применим для неупорядоченной информации, но также можно использовать его и на отсортированных данных. Однако если данные уже отсортированы, можно применить двоичный поиск, который находит данные быстрее.
Последовательный поиск
Последовательный поиск очень легко запрограммировать. Приведенная ниже функция осуществляет поиск в массиве символов известной длины, пока не будет найден элемент с заданным ключом:
/* Последовательный поиск */
int sequential_search(char *items, int count, char key)
{
register int t;
for(t=0; t < count; ++t)
if(key == items[t]) return t;
return -1; /* ключ не найден */
}
Здесь items — указатель на массив, содержащий информацию. Функция возвращает индекс подходящего элемента, если таковой существует, либо -1 в противном случае.
Понятно, что последовательный поиск в среднем просматривает n/2 элементов. В лучшем случае он проверяет только один элемент, а в худшем — n. Если информация хранится на диске, поиск может занимать продолжительное время. Но если данные не упорядочены, последовательный поиск — единственно возможный метод.
Двоичный поиск
Если данные, в которых производится поиск, отсортированы, для нахождения элемента можно применять метод, намного превосходящий предыдущий — двоичный поиск[1]. В нем применяется метод половинного деления. Сначала проверим средний элемент. Если он больше, чем искомый ключ, проверим средний элемент первой половины, в противном случае — средний элемент второй половины. Будем повторять эту процедуру до тех пор, пока искомый элемент не будет найден либо пока не останется очередного элемента.
Например, чтобы найти число 4 в массиве
1 2 3 4 5 6 7 8 9
при двоичном поиске сначала проверяется средний элемент — число 5. Поскольку оно больше, чем 4, поиск продолжается в первой половине:
1 2 3 4 5
Средний элемент теперь равен 3. Это меньше, чем 4, поэтому первая половина отбрасывается. Поиск продолжается в части
4 5
На этот раз искомый элемент найден.
В двоичном поиске количество сравнений в худшем случае равно
log2n
В среднем случае количество немного ниже, а в лучшем — количество сравнений равно 1.
Ниже приведена функция двоичного поиска для массивов символов. Этот поиск можно адаптировать для произвольных структур данных, изменив фрагмент сравнения.
/* Двоичный поиск */
int binary_search(char *items, int count, char key)
{
int low, high, mid;
low = 0; high = count-1;
while(low <= high) {
mid = (low+high)/2;
if(key < items[mid]) high = mid-1;
else if(key > items[mid]) low = mid+1;
else return mid; /* ключ найден */
}
return -1;
}
[1]Есть и другие названия: дихотомический поиск, логарифмический поиск, поиск делением пополам. Этот метод поиска данных состоит в том, что все множество данных делится пополам и определяется, в какой из половин находится искомое данное, после чего половина, в которой находится данное, в свою очередь делится пополам и т.д. Процесс продолжается до тех пор, пока очередное полученное множество не станет равным единственному данному, которое будет искомым, либо будет установлен факт отсутствия искомого данного в этом множестве.