Поиск…
Двоичный поиск
Вступление
Бинарный поиск - это алгоритм поиска Divide и Conquer. Он использует время O(log n) чтобы найти местоположение элемента в пространстве поиска, где n - размер пространства поиска.
Двоичный поиск работает, уменьшая вдвое пространство поиска на каждой итерации после сравнения целевого значения с средним значением пространства поиска.
Чтобы использовать двоичный поиск, пространство поиска должно быть упорядочено (отсортировано) каким-то образом. Дублирующие записи (те, которые сравниваются как равные по сравнению с функцией сравнения) не могут быть различимы, хотя они не нарушают свойство двоичного поиска.
Обычно мы используем меньше (<) в качестве функции сравнения. Если a <b, оно вернет true. если a не меньше b и b не меньше a, a и b равны.
Пример
Вы экономист, но очень плохой. Вам задана задача найти равновесную цену (то есть цену, где спрос = спрос) на рис.
Помните, что чем выше цена, тем больше предложение и тем меньше спрос
Поскольку ваша компания очень эффективна при расчете рыночных сил, вы можете мгновенно получить спрос и предложение в единицах риса, когда цена на рис устанавливается по определенной цене. p
Ваш босс хочет равновесную цену как можно скорее, но говорит вам, что равновесная цена может быть положительным целым числом, которое составляет не более 10^17 и гарантируется, что в диапазоне будет ровно 1 положительное целочисленное решение. Так что идите с вашей работой, прежде чем потерять ее!
Вам разрешено вызывать функции getSupply(k) и getDemand(k) , которые будут выполнять именно то, что указано в задаче.
Пример Объяснение
Здесь наше пространство поиска от 1 до 10^17 . Таким образом, линейный поиск недостижим.
Однако заметьте, что при увеличении k увеличивается значение getSupply(k) и getDemand(k) . Таким образом, для любого x > y getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Поэтому это пространство поиска является монотонным, и мы можем использовать двоичный поиск.
Следующий псевдокод демонстрирует использование двоичного поиска:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
Этот алгоритм работает в ~O(log 10^17) времени. Это может быть обобщена на ~O(log S) времени , где S является размер пространства поиска , поскольку на каждой итерации в while цикла, мы вдвое поисковое пространство (из [низкого: высокая] либо [низкий: средний] или [mid: high] ).
C Реализация двоичного поиска с рекурсией
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
Двоичный поиск: по отсортированным номерам
Проще всего показать двоичный поиск чисел, используя псевдокод
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
Не пытайтесь вернуться раньше, сравнивая массив [mid] с x для равенства. Дополнительное сравнение может только замедлить работу кода. Обратите внимание, что вам нужно добавить один к минимуму, чтобы избежать попадания в ловушку целым делением, всегда округляющимся вниз.
Интересно, что приведенная выше версия бинарного поиска позволяет найти наименьшее количество x в массиве. Если массив содержит дубликаты x, алгоритм может быть слегка изменен, чтобы он мог вернуть наибольшее вхождение x, просто добавив к условию if:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
Обратите внимание, что вместо выполнения mid = (low + high) / 2 также может быть хорошей идеей попробовать mid = low + ((high - low) / 2) для реализаций, таких как реализации Java, чтобы снизить риск получения переполнение для действительно больших входов.
Линейный поиск
Линейный поиск - простой алгоритм. Он перебирает элементы до тех пор, пока запрос не будет найден, что делает его линейным алгоритмом - сложность O (n), где n - количество элементов, которые нужно пройти.
Почему O (n)? В худшем случае вам нужно пройти все n пунктов.
Его можно сравнить с поиском книги в стопке книг - вы просматриваете их все, пока не найдете тот, который вам нужен.
Ниже приведена реализация Python:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
Рабин Карп
Алгоритм Рабина-Карпа или алгоритм Карпа-Рабина представляет собой строковый алгоритм поиска, который использует хеширование для поиска любого из набора строк шаблонов в тексте. Среднее и лучшее время выполнения - O (n + m) в пространстве O ( p), но в худшем случае это O (nm), где n - длина текста, а m - длина рисунка.
Реализация алгоритма в java для сопоставления строк
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
При вычислении хэш-значения мы делим его на простое число, чтобы избежать столкновения. После деления на простое число шансов столкновения будет меньше, но все же существует вероятность того, что значение хэша может быть одинаковым для двух строк, поэтому, когда мы получаем совпадение, мы должны проверить его персонаж по персонажу, чтобы убедиться, что мы получили правильное совпадение.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Это необходимо для пересчета хэш-значения для шаблона, сначала путем удаления самого левого символа, а затем добавления нового символа из текста.
Анализ линейного поиска (худшие, средние и лучшие случаи)
Мы можем иметь три случая для анализа алгоритма:
Худший случай
Средний случай
Лучший случай
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ * Программа драйвера для тестирования вышеперечисленных функций * /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
Худший анализ ситуации (обычно делается)
В худшем случае мы вычисляем верхнюю границу времени работы алгоритма. Мы должны знать случай, который вызывает максимальное количество операций. Для линейного поиска худший случай возникает, когда элемент, который нужно искать (x в приведенном выше коде), отсутствует в массиве. Когда x отсутствует, функции search () сравнивают его со всеми элементами arr [] поочередно. Поэтому наихудшая временная сложность линейного поиска будет равна Θ (n)
Средний анализ ситуации (иногда делается)
При анализе среднего случая мы берем все возможные входы и вычисляем время вычислений для всех входов. Суммируйте все рассчитанные значения и разделите сумму на общее количество входов. Мы должны знать (или предсказывать) распределение дел. Для задачи линейного поиска допустим, что все случаи равномерно распределены (в том числе случай, когда x не присутствует в массиве). Итак, мы суммируем все случаи и делим сумму на (n + 1). Ниже приведено значение средней сложности времени случая.
Лучший анализ случая (Bogus)
В лучшем случае анализа мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, который вызывает минимальное количество операций. В задаче линейного поиска наилучший случай возникает, когда x присутствует в первом местоположении. Количество операций в лучшем случае является постоянным (не зависящим от n). Таким образом, сложность времени в лучшем случае будет равна Θ (1). В большинстве случаев мы делаем анализ худшего случая для анализа алгоритмов. В худшем анализе мы гарантируем верхнюю границу времени работы алгоритма, который является хорошей информацией. Средний случайный анализ непросто сделать в большинстве практических случаев, и это редко делается. В анализе среднего случая мы должны знать (или прогнозировать) математическое распределение всех возможных входов. Анализ наилучшего случая - фиктивный. Гарантия нижней границы алгоритма не дает никакой информации, как в худшем случае, для выполнения алгоритма могут потребоваться годы.
Для некоторых алгоритмов все случаи асимптотически одинаковы, т. Е. Нет худших и лучших случаев. Например, Merge Sort. Merge Sort выполняет операции Θ (nLogn) во всех случаях. Большинство других алгоритмов сортировки имеют худшие и лучшие случаи. Например, в типичной реализации Quick Sort (где точка поворота выбрана как элемент угла) наихудшее происходит, когда входной массив уже отсортирован, и лучше всего возникает, когда опорные элементы всегда делят массив на две половины. Для сортировки вставки худший случай возникает, когда массив сортируется по обратным ссылкам, и лучший случай возникает, когда массив сортируется в том же порядке, что и вывод.