Инструменты пользователя

Инструменты сайта


dvoichnyj_poisk

Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

dvoichnyj_poisk [2010/08/31 07:01] (текущий)
Строка 1: Строка 1:
 +====== Двоичный поиск ======
 +Если у нас есть массив,​ содержащий **упорядоченную** последовательность данных,​ то, в данном случае,​ очень эффективен двоичный поиск.
 +
 +Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Используется в информатике,​ вычислительной математике и математическом программировании.
 +
 +====== Теория двоичного поиска ======
 +Предположим,​ что переменные Lb и Ub содержат,​ соответственно,​ левую и правую границы отрезка массива,​ где находится нужный нам элемент. Поиск мы всегда будем начинать с анализа среднего элемента отрезка массива. Если искомое значение меньше среднего элемента,​ мы переходим к поиску в верхней половине отрезка,​ где все элементы меньше только что проверенного. Другими словами,​ значением Ub становится (M (средний элемент) – 1) и на следующей итерации мы работаем с половиной массива. Таким образом,​ в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере,​ после первой итерации область поиска – всего лишь три элемента,​ после второй остается всего лишь один элемент. Таким образом,​ если длина массива равна 6, нам достаточно трех итераций,​ чтобы найти нужное число. ​
  
загрузка...
dvoichnyj_poisk.txt · Последние изменения: 2010/08/31 07:01 (внешнее изменение)