Двоичный поиск - История изменений

Patarakin: /* Диаграмма бинарного поиска */

2023-11-09T13:03:31Z

Диаграмма бинарного поиска

← Предыдущая версия		Версия от 16:03, 9 ноября 2023
Строка 41:		Строка 41:
	}}		}}

	* [[Binary search (diagram)]] - варианты с определением месяцев в [[~~GraphViz~~]]		* [[Binary search (diagram)]] - варианты с определением месяцев в [[Graphviz]]

	== Пример реализации на Java ==		== Пример реализации на Java ==

Patarakin в 11:41, 14 декабря 2022

2022-12-14T11:41:58Z

@@ Строка 8: / Строка 8: @@
 # Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
-{{#ask: [[Binary search (diagram)]]  | format = embedded}}
+=== Диаграмма бинарного поиска ===
 == Пример реализации на Java ==

Patarakin в 11:30, 2 декабря 2022

2022-12-02T11:30:37Z

← Предыдущая версия		Версия от 14:30, 2 декабря 2022
Строка 8:		Строка 8:
	# Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.		# Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

	({{#ask: [[Binary search (diagram)]] \| format = embedded}});		{{#ask: [[Binary search (diagram)]] \| format = embedded}}


	== Пример реализации на Java ==		== Пример реализации на Java ==

Patarakin в 11:30, 2 декабря 2022

2022-12-02T11:30:03Z

← Предыдущая версия		Версия от 14:30, 2 декабря 2022
Строка 7:		Строка 7:
	# Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.		# Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
	# Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.		# Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

			({{#ask: [[Binary search (diagram)]] \| format = embedded}});

Patarakin в 18:03, 19 октября 2022

2022-10-19T18:03:12Z

← Предыдущая версия		Версия от 21:03, 19 октября 2022
Строка 1:		Строка 1:
	'''Двоичный (бинарный) поиск''' (также известен как '''метод деления пополам''' или '''[[дихотомия]]''') — классический [[алгоритм]] поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в [[информатика\|информатике]], [[вычислительная математика\|вычислительной математике]] и [[математическое программирование\|математическом программировании]].		'''Двоичный (бинарный) поиск''' (также известен как '''метод деления пополам''' или '''[[дихотомия]]''') — классический [[алгоритм]] поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в [[информатика\|информатике]], [[вычислительная математика\|вычислительной математике]] и [[математическое программирование\|математическом программировании]].

	Частным случаем двоичного поиска является [[метод бисекции]], который применяется для поиска корней заданной [[непрерывная функция\|непрерывной функции]] на заданном отрезке.

	== Поиск элемента в отсортированном массиве ==		== Поиск элемента в отсортированном массиве ==

Patarakin в 18:02, 19 октября 2022

2022-10-19T18:02:24Z

@@ Строка 1: / Строка 1: @@
 '''Двоичный (бинарный) поиск''' (также известен как '''метод деления пополам''' или '''[[дихотомия]]''') — классический [[алгоритм]] поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в [[информатика|информатике]], [[вычислительная математика|вычислительной математике]] и [[математическое программирование|математическом программировании]].
@@ Строка 5: / Строка 4: @@
 == Поиск элемента в отсортированном массиве ==
-{{Викиучебник|Реализации алгоритмов/Двоичный поиск}}
 # Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
 # Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
@@ Строка 11: / Строка 10: @@
 # Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
 == Пример реализации на Java ==
@@ Строка 49: / Строка 38: @@
 * Метод используется для нахождения [[экстремум]]а [[целевая функция|целевой функции]] и в этом случае является [[оптимизация (математика)|методом условной одномерной оптимизации]]. Когда функция имеет вещественный аргумент, найти решение с точностью до <math>\varepsilon</math> можно за время <math>\log_2 1 / \varepsilon</math>. Когда аргумент дискретен, и изначально лежит на отрезке длины ''N'', поиск решения займёт <math>1 + \log_2N</math> времени. Наконец, для поиска экстремума, скажем, для определённости [[Экстремум|минимума]], на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:55:03Z

1 версия импортирована

← Предыдущая версия		Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>Mercury: /* Поиск элемента в отсортированном массиве */

2022-09-26T00:23:25Z

Поиск элемента в отсортированном массиве

Новая страница

[[File:Binary Search Depiction.svg|мини|справа|Визуализация бинарного поиска по массиву. Искомое число — 7.]]
'''Двоичный (бинарный) поиск''' (также известен как '''метод деления пополам''' или '''[[дихотомия]]''') — классический [[алгоритм]] поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в [[информатика|информатике]], [[вычислительная математика|вычислительной математике]] и [[математическое программирование|математическом программировании]].

Частным случаем двоичного поиска является [[метод бисекции]], который применяется для поиска корней заданной [[непрерывная функция|непрерывной функции]] на заданном отрезке.

== Поиск элемента в отсортированном массиве ==
{{Викиучебник|Реализации алгоритмов/Двоичный поиск}}
# Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
# Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
# Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
# Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.
* Код <code>(first + last) / 2</code> ошибочен, если <code>first</code> и <code>last</code> по отдельности умещаются в свой тип, а <code>first+last</code> — нет<ref name="joshua">[http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken] {{Wayback|url=http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html |date=20131202222915 }} // Joshua Bloch, Google Research; перевод — [http://habrahabr.ru/post/203398/ Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка] {{Wayback|url=http://habrahabr.ru/post/203398/ |date=20131124053301 }}</ref>. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
** Использовать код <code>first + (last - first) / 2</code>, который точно не приведёт к переполнениям, если имеем дело с неотрицательными целыми числами и first<last.
*** Если <code>first</code> и <code>last</code> — указатели или [[итератор]]ы, такой код единственно правильный, поскольку не нарушает абстракцию (уже операция «указатель + указатель» некорректна). Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «указатель+число → указатель», «указатель−указатель → число».
** Если <code>first</code> и <code>last</code> — типы со знаком, провести расчёт в беззнаковом типе: <code>((unsigned)first + (unsigned)last) / 2</code>. В [[Java]] сработает такой код: <code>(first + last) >>> 1</code> (знаковое двоичное сложение совпадает с беззнаковым, Java гарантирует такое поведение даже при переполнении, и вся эта формула оперирует знаковыми числами как беззнаковыми).
** Написать расчёт на ассемблере, с использованием [[флаг переноса|флага переноса]]. Что-то наподобие <code>add eax, b; rcr eax, 1</code>. А вот [[длинная арифметика|длинные типы]] использовать нецелесообразно, <code>first + (last - first) / 2</code> быстрее.
* В двоичном поиске часты [[ошибка на единицу|ошибки на единицу]], и каждая такая ошибка превращается в [[зацикливание]], пропуск или выход за пределы массива. Поэтому важно протестировать такие случаи: пустой массив (<code>n=0</code>), один элемент (<code>n=1</code>), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент.
* Иногда требуется, чтобы, если <code>x</code> в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не <code>x</code>, а следующий за ним элемент).<ref>В [[C++]] <code>std::lower_bound</code> находит первое вхождение <code>x</code>, а <code>std::upper_bound</code> — элемент, следующий за <code>x</code>.</ref> Например, функция {{cpp|std::lower_bound}} из [[C++]] находит первый из равных, а {{cpp|std::upper_bound}} — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.

Учёный [[Бентли, Йон|Йон Бентли]] утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.

== Пример реализации на Java ==
<syntaxhighlight lang="java" line="1">
int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = arr[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
</syntaxhighlight>

== Приложения ==
Практические приложения метода двоичного поиска разнообразны:
* Широкое распространение в [[информатика|информатике]] применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по [[ключ (указатель)|ключу]], присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
* Также его применяют в качестве [[численные методы|численного метода]] для нахождения приближённого решения уравнений (см. [[Метод бисекции]]).
* Метод используется для нахождения [[экстремум]]а [[целевая функция|целевой функции]] и в этом случае является [[оптимизация (математика)|методом условной одномерной оптимизации]]. Когда функция имеет вещественный аргумент, найти решение с точностью до <math>\varepsilon</math> можно за время <math>\log_2 1 / \varepsilon</math>. Когда аргумент дискретен, и изначально лежит на отрезке длины ''N'', поиск решения займёт <math>1 + \log_2N</math> времени. Наконец, для поиска экстремума, скажем, для определённости [[Экстремум|минимума]], на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

== См. также ==
* [[Линейный поиск]]
* [[Метод бисекции]]
* [[Метод дихотомии]]
* [[Метод Ньютона]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]

== Примечания ==
{{примечания}}

== Литература ==
* {{source|Q21694522|part=Глава 4. Метод декомпозиции: Бинарный поиск|pages=180—183}}
* {{книга|автор = Амосов А. А., Дубинский Ю. А., Копченова Н. П.|заглавие = Вычислительные методы для инженеров|оригинал = |ссылка
|издание = |место = М.|издательство = Мир|год = 1998|страницы =|isbn = }}
* {{книга|автор = Бахвалов Н. С., [[Жидков, Николай Петрович|Жидков Н. П.]], Кобельков Г. Г.|заглавие = Численные методы|оригинал = |ссылка = |издание = 8-е изд|место = М.|издательство = Лаборатория Базовых Знаний|год = 2000|страницы =|isbn = }}
* {{книга
|автор = Вирт Н.
|часть =
|заглавие = Алгоритмы + структуры данных = программы
|оригинал =
|ссылка =https://archive.org/details/libgen_852
|место = М.
|издательство = «[[Мир (издательство)|Мир]]»
|год = 1985
|страницы = [https://archive.org/details/libgen_852/page/n31 28]
|isbn =
}}
* {{книга|автор = Волков Е. А.|заглавие = Численные методы|оригинал = |ссылка = |издание =|место = М.|издательство = Физматлит|год = 2003|страницы =|isbn = }}
* {{книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }}
* {{книга:CLRS|2005}}
* {{книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка = |издание = |место = М.|издательство = Наука|год = 1970|страницы = 575-576|isbn = }}
* {{книга|автор = Коршунов Ю. М., Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }}
* {{книга|автор = Максимов Ю. А., Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }}
* {{книга
|заглавие = Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск
|оригинал = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching
|автор = Роберт Седжвик.
|страницы = 672
|год = 2003
|место = СПб.
|издательство = ДиаСофтЮП
|isbn = 5-93772-081-4
}}

== Ссылки ==
* [http://algolist.manual.ru Материал на сайте algolist]
* [http://kvodo.ru/dvoichnyiy-poisk.html Пошаговый разбор алгоритма, коды программ]
* [http://habrahabr.ru/post/91698/ Как же все-таки правильно написать двоичный поиск?]

[[Категория:Алгоритмы оптимизации]]
[[Категория:Алгоритмы поиска]]