Алгоритм бинарного поиска (АБП):
Бинарный поиск осуществляется на отсортированном списке. Идея в
том, что список делится пополам, берется средний эл-т и сравнивается с целевым
эл-том. При сравнении возможен один из трех результатов: значения равны,
целевое значение меньше элемента списка, либо целевое значение больше элемента
списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях
мы можем отбросить половину списка. Когда целевое значение меньше среднего
элемента, мы знаем, что если оно имеется в списке, то находится перед этим
средним элементом. Когда же оно больше среднего элемента, мы знаем, что если
оно имеется в списке, то находится после этого среднего элемента. Этого
достаточно, чтобы мы могли одним сравнением отбросить половину списка. При
повторении этой процедуры мы сможем отбросить половину оставшейся части списка.
В наихудшем случае число проходов равно k = log2(N +1).
Средний случай A(N)≈ log2(N +1)-1
Анализ
сложности – Королев-Миков страницы 122!!!
