# Поиск границ с использованием двоичного поиска

## Поиск левой границы

!!! question

    Дан упорядоченный массив `nums` длиной $n$, который может содержать повторяющиеся элементы. Необходимо вернуть индекс самого левого элемента `target` в массиве. Если массив не содержит этот элемент, вернуть $-1$.

Вспомним метод поиска точки вставки с использованием двоичного поиска: после завершения поиска $i$ указывает на самый левый `target`, **поэтому поиск точки вставки по сути является поиском индекса самого левого** `target`.

Рассмотрим реализацию поиска левой границы через функцию поиска точки вставки. Обратите внимание, что массив может не содержать `target`, что может привести к следующим двум результатам:

- Индекс точки вставки $i$ выходит за границы массива.
- Элемент `nums[i]` не равен `target`.

При возникновении любой из этих двух ситуаций можно просто вернуть $-1$. Код приведен ниже:

```src
[file]{binary_search_edge}-[class]{}-[func]{binary_search_left_edge}
```

## Поиск правой границы

Как же найти самый правый `target`? Самый прямой способ -- изменить код, заменив операцию сужения указателей в случае `nums[m] == target`. Код здесь опущен, заинтересованные читатели могут реализовать его самостоятельно.

Ниже мы рассмотрим два более изящных метода.

### Повторное использование поиска левой границы

На самом деле мы можем использовать функцию поиска самого левого элемента для поиска самого правого элемента, конкретный метод: **преобразовать поиск самого правого** `target` **в поиск самого левого** `target + 1`.

Как показано на рисунке ниже, после завершения поиска указатель $i$ указывает на самый левый `target + 1` (если он существует), а $j$ указывает на самый правый `target`, **поэтому достаточно вернуть** $j$.

![Преобразование поиска правой границы в поиск левой границы](../assets/binary_search_right_edge_by_left_edge.png)

Обратите внимание, что возвращаемая точка вставки -- это $i$, поэтому необходимо вычесть из нее $1$, чтобы получить $j$:

```src
[file]{binary_search_edge}-[class]{}-[func]{binary_search_right_edge}
```

### Преобразование в поиск элемента

Мы знаем, что когда массив не содержит `target`, в конечном итоге $i$ и $j$ будут указывать соответственно на первый элемент, больший и меньший `target`.

Поэтому, как показано на рисунке ниже, мы можем создать элемент, которого не существует в массиве, для поиска левой и правой границ.

- Поиск самого левого `target`: можно преобразовать в поиск `target - 0.5` и вернуть указатель $i$.
- Поиск самого правого `target`: можно преобразовать в поиск `target + 0.5` и вернуть указатель $j$.

![Преобразование поиска границ в поиск элемента](../assets/binary_search_edge_by_element.png)

Код здесь опущен, следует отметить следующие два момента:

- Данный массив не содержит дробных чисел, что означает, что нам не нужно беспокоиться о том, как обрабатывать случай равенства.
- Поскольку этот метод вводит дробные числа, необходимо изменить тип переменной `target` в функции на тип с плавающей точкой (в Python изменения не требуются).