Бинарный поиск - История изменений

Ctrlalt в 14:59, 24 мая 2023

2023-05-24T14:59:01Z

← Предыдущая версия		Версия от 14:59, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==

			<youtube width="300" height="180">q06xEZ7coR0</youtube>
			<youtube width="300" height="180">DkPjtl5fkks</youtube>
			<youtube width="300" height="180">_u2yypDA6R0</youtube>

			<youtube width="300" height="180">mvC_9pKG3uQ</youtube>
			<youtube width="300" height="180">rmWhWsPg2MA</youtube>
			<youtube width="300" height="180">8WE6cIrqb6M</youtube>

	== Бинарный поиск элемента в отсортированном массиве ==		== Бинарный поиск элемента в отсортированном массиве ==

Ctrlalt: /* Ссылки */

2021-08-14T07:41:39Z

Ссылки

← Предыдущая версия		Версия от 07:41, 14 августа 2021
Строка 335:		Строка 335:
	* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]		* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]
	* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]		* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]
	* [~~http~~://~~github~~.~~com/petr-kalinin/progtexts~~/~~releases/download/v2014.11.01~~/~~07_binsearch~~.~~pdf~~ Калинин П. ~~— Двоичный~~ поиск]		* [https://notes.algoprog.ru/binsearch/07_binsearch_main.html Калинин П. — Бинарный поиск]
	* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]		* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]
	Код:		Код:

Ctrlalt: /* Ссылки */

2020-08-21T04:50:10Z

Ссылки

← Предыдущая версия		Версия от 04:50, 21 августа 2020
Строка 330:		Строка 330:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
			* [https://codeforces.com/edu/course/2/lesson/6 Codeforces EDU — Двоичный поиск]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Целочисленный двоичный поиск]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Целочисленный двоичный поиск]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Вещественный двоичный поиск]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Вещественный двоичный поиск]
	* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]		* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]
	* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]		* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]
	* [https://codeforces.com/edu/course/2/lesson/6 Codeforces EDU — Двоичный поиск]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]
	* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]		* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]

Ctrlalt: /* Ссылки */

2020-08-21T04:39:11Z

Ссылки

← Предыдущая версия		Версия от 04:39, 21 августа 2020
Строка 334:		Строка 334:
	* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]		* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]
	* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]		* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]
			* [https://codeforces.com/edu/course/2/lesson/6 Codeforces EDU — Двоичный поиск]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]
	* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]		* [http://brilliant.org/wiki/binary-search/ Brilliant.org — Binary Search]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~BinarySearch~~.~~java~~ CodeLibrary ~~—~~ Binary search]		* [https://github.com/indy256/codelibrary/blob/master/cpp/misc/binary_search.cpp CodeLibrary — Binary search]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 2]		* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 2]

Ctrlalt: /* Правила написания бинарного поиска без головной боли */

2020-02-15T10:54:14Z

Правила написания бинарного поиска без головной боли

← Предыдущая версия		Версия от 10:54, 15 февраля 2020
Строка 325:		Строка 325:
	return -1;		return -1;
	\|}		\|}

			При желании [[Бинарный поиск в интервале\|показанный алгоритм можно оптимизировать]], сократив количество проверок в конце.

	== Ссылки ==		== Ссылки ==

Ctrlalt: /* Ссылки */

2020-02-14T23:02:05Z

Ссылки

← Предыдущая версия		Версия от 23:02, 14 февраля 2020
Строка 330:		Строка 330:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Целочисленный двоичный поиск]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Целочисленный двоичный поиск]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Вещественный двоичный поиск]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA neerc.ifmo.ru/wiki — Вещественный двоичный поиск]
	* [http://brestprog.~~neocities.org~~/~~lections~~/binsearch~~.html~~ brestprog~~.neocities.org —~~ Бинарный поиск]		* [http://brestprog.by/topics/binsearch/ brestprog — Бинарный поиск]
	* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]		* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]

Ctrlalt: /* Правила написания бинарного поиска без головной боли */

2020-02-14T22:46:39Z

Правила написания бинарного поиска без головной боли

← Предыдущая версия		Версия от 22:46, 14 февраля 2020
Строка 149:		Строка 149:
	int m = l + (r - l) / 2;		int m = l + (r - l) / 2;
	if (<span style="color:red">a[m] <= x</span>) // if (<span style="color:red">a[m] > x</span>)		if (<span style="color:red">a[m] <= x</span>) // if (<span style="color:red">a[m] > x</span>)
	l = m; // r = m;		l = m; // r = m;
	else // else		else // else
	r = m; // l = m;		r = m; // l = m;
	}		}
	<span style="color:orange">if (a[l] > x)</span>		<span style="color:orange">if (a[l] > x)</span>
Строка 165:		Строка 165:
	int m = l + (r - l) / 2;		int m = l + (r - l) / 2;
	if (<span style="color:red">a[m] < x</span>) // if (<span style="color:red">a[m] >= x</span>)		if (<span style="color:red">a[m] < x</span>) // if (<span style="color:red">a[m] >= x</span>)
	l = m; // r = m;		l = m; // r = m;
	else // else		else // else
	r = m; // l = m;		r = m; // l = m;
	}		}
	<span style="color:orange">if (a[l] >= x)</span>		<span style="color:orange">if (a[l] >= x)</span>
Строка 181:		Строка 181:
	int m = l + (r - l) / 2;		int m = l + (r - l) / 2;
	if (<span style="color:red">a[m] < x</span>) // if (<span style="color:red">a[m] >= x</span>)		if (<span style="color:red">a[m] < x</span>) // if (<span style="color:red">a[m] >= x</span>)
	l = m; // r = m;		l = m; // r = m;
	else // else		else // else
	r = m; // l = m;		r = m; // l = m;
	}		}
	<span style="color:orange">if (a[l] == x)</span>		<span style="color:orange">if (a[l] == x)</span>

Ctrlalt: /* Правила написания бинарного поиска без головной боли */

2020-02-14T22:36:26Z

Правила написания бинарного поиска без головной боли

Внесённые изменения

Ctrlalt в 22:16, 14 февраля 2020

2020-02-14T22:16:04Z

Внесённые изменения

Ctrlalt в 21:48, 14 февраля 2020

2020-02-14T21:48:04Z

Внесённые изменения