Базы данных существуют для того, чтобы время от времени пользователи могли найти нужную запись, введя ее ключ. Существует один метод поиска информации в неупорядоченном массиве, и другой для поиска в упорядоченном массиве. В набор стандартной библиотеки компиляторов языка С входит стандартная функция 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]Есть и другие названия: дихотомический поиск, логарифмический поиск, поиск делением пополам. Этот метод поиска данных состоит в том, что все множество данных делится пополам и определяется, в какой из половин находится искомое данное, после чего половина, в которой находится данное, в свою очередь делится пополам и т.д. Процесс продолжается до тех пор, пока очередное полученное множество не станет равным единственному данному, которое будет искомым, либо будет установлен факт отсутствия искомого данного в этом множестве.