Лекция
Привет, сегодня поговорим про методы поиска, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое методы поиска, последовательный поиск, двоичный поиск, дихотомический поиск , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
Базы данных существуют для того, чтобы время от времени пользователи могли найти нужную запись, введя ее ключ. Существует один метод поиска информации в неупорядоченном массиве, и другой для поиска в упорядоченном массиве. В набор стандартной библиотеки компиляторов языка С входит стандартная функция bsearch(). Тем не менее, как и в случае сортировки, процедуры общего назначения иногда совсем не эффективны при использовании в критических ситуациях из-за накладных расходов, связанных с их обобщением. Кроме того, функцию bsearch() невозможно применить к неупорядоченным данным.
Для нахождения информации в неупорядоченном массиве требуется последовательный поиск , начинающийся с первого элемента и заканчивающийся при обнаружении подходящих данных либо при достижении конца массива. Этот метод применим для неупорядоченной информации, но также можно использовать его и на отсортированных данных. Однако если данные уже отсортированы, можно применить двоичный поиск , который находит данные быстрее.
Последовательный поиск очень легко запрограммировать. Об этом говорит сайт https://intellect.icu . Приведенная ниже функция осуществляет поиск в массиве символов известной длины, пока не будет найден элемент с заданным ключом:
/* Последовательный поиск */
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. Если информация хранится на диске, поиск может занимать продолжительное время. Но если данные не упорядочены, последовательный поиск — единственно возможный метод.
Если данные, в которых производится поиск, отсортированы, для нахождения элемента можно применять метод, намного превосходящий предыдущий — двоичный поиск . В нем применяется метод половинного деления. Сначала проверим средний элемент. Если он больше, чем искомый ключ, проверим средний элемент первой половины, в противном случае — средний элемент второй половины. Будем повторять эту процедуру до тех пор, пока искомый элемент не будет найден либо пока не останется очередного элемента.
Например, чтобы найти число 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;
}
Есть и другие названия: дихотомический поиск , логарифмический поиск, поиск делением пополам. Этот метод поиска данных состоит в том, что все множество данных делится пополам и определяется, в какой из половин находится искомое данное, после чего половина, в которой находится данное, в свою очередь делится пополам и т.д. Процесс продолжается до тех пор, пока очередное полученное множество не станет равным единственному данному, которое будет искомым, либо будет установлен факт отсутствия искомого данного в этом множестве.
На этом все! Теперь вы знаете все про методы поиска, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое методы поиска, последовательный поиск, двоичный поиск, дихотомический поиск и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про методы поиска
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов