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

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


dvoichnyj_poisk

Различия

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

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

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