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

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

Варианты задачи:

Массив 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;

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

Навигация

Поиск