Ctrlalt: Новая страница: «В основной статье мы рассмотрели, как писать бинарный поиск до двух эле…»

2020-02-15T10:49:37Z

Новая страница: «В основной статье мы рассмотрели, как писать бинарный поиск до двух эле…»

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

В [[Бинарный поиск|основной статье]] мы рассмотрели, как писать бинарный поиск до двух элементов и проверять их отдельно. Эту реализацию при желании можно оптимизировать.

Варианты задачи:
# Массив a[] отсортирован так, что функция f(a[i]) возвращает сначала true, затем false. Нужно найти последний элемент, для которого f(a[i]) == true;
# Массив a[] отсортирован так, что функция f(a[i]) возвращает сначала false, затем true. Нужно найти первый элемент, для которого f(a[i]) == true.

Правила:
* Поиск производится не в отрезке [l; r], а в '''интервале''' (l; r). Начальные значения: l = -1, r = size. Считаем, что начальный l даёт true, начальный r — false (или наоборот, в зависимости от варианта задачи);
* Поиск всегда осуществляется до двух элементов (while (l + 1 < r)). Между этими элементами будет проходить граница true и false (false и true);
* После проверки среднего элемента границы всегда смещаются только на середину (l = m или r = m, никаких плюс-минус единиц);
* Смещение границ должно происходить так, чтобы не потерять искомый элемент;
* Когда цикл завершится, если мы искали последний элемент, то нам нужен l, если первый — то r. Здесь нужно проверить, что l или r не равен -1 или size. В ряде случаев нужно проверить, что для выбранного элемента выполняется некоторое условие (например, мы искали первый элемент, равный x, а найдём первый элемент, больший или равный x, и равенство нужно проверить отдельно).

Первый вариант задачи:
{|
|
// f() возвращает
// сначала true, потом false
// последний f() == true
int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (f(a[m]))
l = m;
else
r = m;
}
if (l != -1)
return l;
return -1;
|
// сорт. по неубыванию
// последний элемент < x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] < x)
l = m;
else
r = m;
}
if (l != -1)
return l;
return -1;
|
// сорт. по неубыванию
// последний элемент <= x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= x)
l = m;
else
r = m;
}
if (l != -1)
return l;
return -1;
|
// сорт. по неубыванию
// последний элемент == x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= x)
l = m;
else
r = m;
}
if (l != -1 && a[l] == x)
return l;
return -1;
|}

Второй вариант задачи:
{|
|
// f() возвращает
// сначала false, потом true
// первый f() == true
int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (f(a[m]))
r = m;
else
l = m;
}
if (r != size)
return r;
return -1;
|
// сорт. по неубыванию
// первый элемент > x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] > x)
r = m;
else
l = m;
}
if (r != size)
return r;
return -1;
|
// сорт. по неубыванию
// первый элемент >= x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] >= x)
r = m;
else
l = m;
}
if (r != size)
return r;
return -1;
|
// сорт. по неубыванию
// первый элемент == x

int l = -1, r = size;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] >= x)
r = m;
else
l = m;
}
if (r != size && a[r] == x)
return r;
return -1;
|}

* [http://algorithmica.org/tg/binary-search algorithmica.org — Бинарный поиск]
* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/07_binsearch.pdf Калинин П. — Двоичный поиск]

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

Ctrlalt: Новая страница: «В основной статье мы рассмотрели, как писать бинарный поиск до двух эле…»