Бинарный поиск

1. Бинарный поиск

2. ОПРЕДЕЛЕНИЕ

Бинарный поиск –
алгоритм поиска
элемента в
отсортированном
массиве. Основа
метода – деление
массива (области
поиска) на половины.

3. Алгоритм

1)
Проверить, что искомое значение
не выходит за границы области
поиска;
2)
Найти середину области поиска;
3)
Если искомое значение больше,
чем значение в середине области,
то повторяем поиск в области от
середины до наибольшего
значения области, иначе – от
наименьшего до середины.

4.

Начало
a[n], x, f,
l
нет
нет
l-f<1
mid=lastfirst/2
нет
binary_sea
rh(x,a[n],f,l
-m)
x>a[f+m]
нет
res=-1
да
да
да
x==f
x==l
да
binary_sea
rh(x,a[n],f
+m,l)
x<f
x>l
res=-1
да
res=f
res=l
Конец

5. ПРИМЕР РЕАЛИЗАЦИИ

int binary_search (int value, int *array, int *first, int *last){
if ((value>*(last))||(value<*first))
return -1;
else if (last-first==1)
{
if (*first==value) return array-first;
else if (*(last)==value) return last-array;
else return -1;
}
else {
unsigned int mid = (last - first) / 2;
if (value > *(first + mid))
return binary_search(value, array, first + mid, last);
else
return binary_search(value, array, first, last - mid);
}
}

6. ТИПИЧНЫЕ ОШИБКИ

1)
first+last вызывает выход за границы диапазона
используемого типа данных. Решается
использованием указателей или итераторов.
2)
Ошибки на единицу.
3)
Ищется не первое/последнее значение.

7. STL

bool binary_search – возвращает истину, если
искомый элемент встречается в массиве и ложь
в противном случае.
binary_search(array_100,array_100+100,63);

8. СКОРОСТЬ РАБОТЫ

Число итераций для поиска некоторого числа в
массиве
Бинарный поиск
Линейный поиск
7
10
14
57
500
6005
17
20025
Сложность линейного поиска – O(n)
Сложность бинарного поиска – O(log2n)

9. Замечания

Значение mid – не обязательно середина массива. Оно
определяется как граница раздела двух областей
поиска – той, в которой будет продолжен поиск, и той,
которая будет отброшена.
Большинство задач на бинарный поиск подразумевают
именно правильное определение mid.
Единого алгоритма для данного алгоритма не
существует. В каждом случае mid определяется только
на основе анализа задачи.

10. Замечания

Бинарный поиск работает с любыми структурами
данных, которые расположены в памяти
последовательно и отсортированы.
В случае использования таких структур данных, как
стек, очередь, дерево и т.д. бинарный поиск не работает.

11. Замечания

Бинарный поиск можно использовать для
монотонных функций.
Функция монотонна в том случае, если она
всё время не убывает или не возрастает.
Примеры – линейная, кубическая,
логарифм, экспонента.
30
25
20
15
10
5
0
0
2
линейная
4
кубическая
6
8
натуральный логарифм
10
12
экспонента

12. Литература

Кнут, «Искусство программирования», том 3;
Лафоре, «Структуры данных и алгоритмы Java» (тут
хватит и знаний C++).
Вирт Н. Алгоритмы + структуры данных = программы.