|
2 Лабораторная работа.
Тема: Бинарный поиск.
Поиск.
1.Поиск – это поиск заданного количества элементов в заданном множестве. Например, поиск числа в элементах массива.
2. Массив: 45, 12, 89, 12, -78, 12;
3. Позиции числа 12 – 2, 4, 6;
4.При простом линейном поиске мы проверяем каждый элемент массива.
5. Над каждым запросом выполняется O (n) операций.
Недостатком линейного поиска является то, что при количестве запросов m общее количество сравнений будет n*m, так как для каждого запроса требуется n операций. Если n = m = 105, то требуется 1010 операций. И EXM не может сделать это за короткое время. Поэтому мы используем бинарный поиск.
Бинарный поиск
1. Нам дан одномерный массив, отсортированный по возрастанию:
2.4 6 8 10 15 20 21 50 63
3.И дается число. Цель состоит в том, чтобы определить, существует ли это число в данном массиве. Удалите его позицию, если таковая имеется. Например, число 10 находится в массиве, а позиция равна 4. Число 16 не входит в массив. Если его нет в массиве, вы можете вернуть, например, -1.
4.Если мы ответим O (n) на каждый запрос линейным поиском, потребуется O (nm) операции, если количество вопросов равно m.
5. Алгоритм бинарного поиска позволяет быстро найти ответ на каждый вопрос.
Давайте посмотрим, как работает этот алгоритм:
6. У нас всегда есть три числа: это пределы индексов массива, которые ищет элемент: индексы L (левый, левый) и R (правый, правый) и искомое число x; Первоначально L = 1, R = n + 1; Правый индекс не принадлежит. Итак, сначала мы ищем число во всем массиве. Правая граница — это первый индекс справа от массива, и он не принадлежит данному массиву.
Каждый раз, когда мы выбираем элемент из данного раздела и сравниваем его с искомым элементом.
Индекс элемента в середине: m = (L + R) / 2;
Если элемент в середине больше искомого числа, мы ограничиваем поиск справа. l Поскольку массив отсортирован в порядке убывания, элемент в середине больше искомого числа, поэтому все числа справа от него больше искомого числа, и они нам больше не нужны. Переход к интервалу, который вы ищете [L, m].
В противном случае я ограничиваю влево. Интервал, который вы ищете, смещается на [m, R].
Это означает, что длина искомого интервала в каждой практике уменьшается в 2 раза. Если оно уменьшается в 2 раза при каждой операции, то после каждой операции оно уменьшается в 2к раз. Поскольку длина интервала изначально равна n, мы определяем количество операций, необходимых для его сокращения до 1, следующим образом.
2k = n => k = log2 (n). То есть общее количество операций равно log(n). Когда значение этой асаны составляет около 105, оно составляет около 17. Это означает, что в алгоритме бинарного поиска на каждый поисковый запрос можно ответить, выполнив столько же операций.
Например, давайте посмотрим на число 22:
Так как элемент в середине 17, 22-17 продолжаем искать его справа.
Теперь элемент в середине равен 30. Так как это 22 < 30, мы теперь ищем его слева.
На этот раз элемент в середине 22≥22, так что теперь мы продолжим поиск с интервала справа.
Поскольку элемент в середине 25, 22 < 25, продолжаем интервал слева.
В итоге границы искомого интервала сошлись в одной точке, т. е. R = L + 1. Изначально мы сделали индекс R индексом, который не принадлежит массиву. Индекс искомого массива равен L. Мы нашли этот индекс, но отслеживаемый номер может отсутствовать в массиве. Чтобы это проверить, достаточно проверить, что элемент массива в найденном индексе равен искомому числу, то есть если (a[L] == x).
Если мы ищем пропущенное число, например, 23, происходит тот же процесс, и результирующий индекс равен 9.
Код бинарного поиска на C++:
int binsearch(int x, int left, int right) {
while (right-left > 1) {
int middle = (left+right) / 2;
if (a[middle] > x)
right = middle;
else
left = middle;
}
if (a[left]==x)
return left;
return -1;
}
В основной части программы учим элементы массива и обращаемся к функции:
cout << binsearch (x, 1, n + 1);
Если число x присутствует в массиве, то это индекс массива, за которым оно стоит, в противном случае
Выводит число -1.
Двоичный поиск, когда элементы массива не уникальны.
Дан массив, отсортированный в порядке убывания.
Элементы массива могут повторяться, то есть число может участвовать в массиве более одного раза.
Необходимо найти заданный элемент, если он есть, чтобы извлечь его начальный и конечный индексы.
Например:
лабораторная работа 2.
Ответ:
#include
using namespace std;
int w[100001], s[100001];
int fun( int ch , int on , int x ){
while(on-ch>1){
int m=(on+ch)/2;
if(w[m]==x)
{
return m;
}
if(w[m]
{
ch=m;}
else
{
on=m;}
}
return 0;
}
main()
{
int n,i,j,m;
cin>>n;
for(i=1; i<=n ; i++){
cin>>w[i];
}
cin>>m;
int c,k=0;
for(j=1; j<=m; j++){
cin>>s[j];
int d=fun(1,n,s[j]);
if(d>0){k++;}
}
if(k==0) cout<<0;
else cout<
}
Do'stlaringiz bilan baham: |
