Поиск

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

На этот раз искомый элемент найден.

В двоичном поиске количество сравнений в худшем случае равно

log₂n

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