Алгоритмы поиска
В программировании одной из наиболее часто встречающихся задач является поиск. При решении таких задач мы исходим из предположения, что группа данных, в которой необходимо найти заданный элемент, является фиксированной.
Пример: Пусть задан массив из n элементов array[0...n-1]. Обычно items описывает запись с некоторым полем, выполняющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска x (a[i], key = x). Полученный в результате i, удовлетворяющий условию a[i] = key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, то мы будем считать, что тип item включает только ключ (item = key).
1. Линейный поиск
Линейный поиск заключается в простом, последовательном просмотре массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Условием окончания поиска является либо нахождение элемента, либо просмотр всего массива без обнаружения совпадений. Этот метод просто проверяет каждый элемент массива по очереди, пока не найдет искомый элемент или не просмотрит весь массив.
Линейный поиск
int i = 0;
const int n = 100;
int arr[n] = {...};
int x;
cin >> x;
while((i < n) && (arr[i] != x)) {
i += 1;
}
2. Линейный поиск с барьером
При линейном поиске на каждом шаге требуется вычислять логические выражения и увеличивать индекс. Чтобы увеличить скорость поиска, можно упростить само логическое выражение. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого в конец массива достаточно поместить дополнительный элемент x. Такой вспомогательный элемент называется барьером. Он охраняет нас от перехода за пределы массива. Этот метод упрощает линейный поиск, добавляя искомый элемент в конец массива. Это гарантирует, что поиск всегда будет успешным, и упрощает условие окончания поиска.
const int n = 100;
int arr[n] = {0...n};
int x;
cin >> x;
arr[n] = x;
int i = 0;
while (arr[i] != x) i += 1;
3. Бинарный поиск
Для рассмотрения алгоритма мы будем считать, что массив будет заранее упорядочен, то есть удовлетворяет условию 1 <= k < N; a[k-1] <= a[k]. Основная идея алгоритма выбрать случайно некоторый элемент, предположим a[m] и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается. Если меньше x, то мы заключаем, что все элементы с индексами <= m можно исключить из дальнейшего поиска. Это соображение приводит нас к алгоритму, который называется поиск делением пополам. Этот метод использует преимущество отсортированного массива, чтобы ускорить поиск. Он выбирает элемент в середине массива и сравнивает его с искомым. Если элемент в середине меньше искомого, то поиск продолжается в правой половине массива. Если элемент в середине больше искомого, то поиск продолжается в левой половине массива. Этот процесс повторяется, пока не будет найден искомый элемент или пока не останется непроверенных элементов.
int n = 100, left = 0, right = n - 1;
int arr[n] = {0...n};
int x;
bool found = false;
cout << "Введите число для поиска: ";
cin >> x;
while(left <= right && !found) {
int m = (left+right)/2;
if(arr[m] == x) {
found = true;
cout << "Число найдено на позиции: " << m << endl;
}
else if(arr[m] < x) left = m + 1;
else right = m - 1;
}
if(!found) {
cout << "Число не найдено." << endl;
}
Бинарный поиск
Эффективность алгоритма можно несколько улучшить, если поменять местами заголовки условных операторов. Проверку на равенство можно выполнить во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы.
Поиск в таблице
Поиск в массиве = поиск в таблице. Особенно если ключ сам является составным объектом, таким как массив чисел или массив символов. Часто встречается поиск символов, когда массив символов называют строками или словами. Строковый тип определяется так, string = char arr[0...n-1]. Для установки факта совпадения, мы должны убедиться, что все символы сравниваемых строк соответственно равны один к другому, поэтому сравнение составных операндов сводится к поиску их на неравенство. Если нет не равных частей, то это равенство. Чаще всего используется 2 представления о размерах строк. 1) Размер указывается неявно, благодаря добавлению кольцевого символа, который больше нигде не употребляется. Обычно используется непечатаемый символ со значением 0C ('/0') (минимальный символ из всех символов). 2) Размер явно хранится в качестве первого элемента массива, то есть строка s имеет вид s = s0, s1, ..., s(n-1). Эти символы являются фактическими в строке, а s0 = char(n) (определяет размер строки). Этот метод аналогичен поиску в массиве, но применяется к строкам. Здесь мы ищем подстроку в строке, сравнивая каждый символ подстроки с соответствующим символом строки.
Задача: упорядоченная таблица T (в алфавитном порядке); Аргумент поиска = x (string); T = string arr[0...n-1]. N достаточно велико.
int n = ...; // Замените на конкретное значение
string arr[n] = {...}; // Замените на конкретные значения
string x;
int l = 0, r = n;
cout << "Введите строку для поиска: ";
cin >> x;
while(l < r) {
int m = (l + r) / 2;
if(arr[m] == x) {
cout << "Строка найдена на позиции: " << m << endl;
break;
}
else if(arr[m] < x) l = m + 1;
else r = m;
}
if(l == r) {
cout << "Строка не найдена." << endl;
}
Прямой поиск строки
Пусть задан массив s из n элементов. И задан массив p из m элементов. 0 < m <= n. s: array[0...n-1] of item, p: array[0...n-1] of item. Поиск строки обнаруживает первое вхождение p в s. Обычно item это символы, то есть их можно считать некоторым текстом, а p является образом или словом. Мы хотим найти первое вхождение в слово. Рассмотрим прямолинейный поиск алгоритма. Поиск можно представить, как повторяющие сравнения. Этот метод ищет первое вхождение подстроки в строке, сравнивая каждый символ подстроки с соответствующим символом строки.
string P = "..."; // Замените на искомую строку
string T = "..."; // Замените на текст, в котором ищем
int M = P.size();
int N = T.size();
bool found = false;
for(int i = 0; i <= N - M && !found; i++) {
int j = 0;
while(j < M && T[i + j] == P[j]) {
j++;
}
if(j == M) {
found = true;
cout << "Строка найдена на позиции: " << i << endl;
}
}
if(!found) {
cout << "Строка не найдена." << endl;
}
