Алгоритм бинарного поиска в массиве на Python (две фиктивные границы)

Линейный поиск элемента в массиве

Необходимо создать функцию, которая проверяет, присутствует ли заданный элемент `key` в списке `A`. Функция должна возвращать `True` или `False`. Это можно сделать с помощью цикла `for`, включая проверку условия:

```python

def search(A, key):

     for i in range(len(A)):

          if A[i] == key:

               return True

               return False

```

Также можно реализовать функцию с использованием цикла `while`, без условий в его теле:

```python

def search(A, key):

     i = 0

     while i < len(A) and A[i] != key:

          i += 1

     return i < len(A)

```

Каждая из этих функций также может возвращать индекс найденного элемента или специальное значение, например, `-1`, если элемент не найден:

```python

def search(A, key):

     for i in range(len(A)):

          if A[i] == key:

          return i

     return -1

```

Аналогичная реализация может быть выполнена с помощью цикла `while`:

```python

def search(A, key):

     i = 0

     while i < len(A) and A[i] != key:

          i += 1

     if i < len(A):

          return i

     else:

          return -1

```

Все эти алгоритмы должны пройти через весь список, чтобы найти заданный элемент, поэтому их временная сложность составляет O(n), где n — это длина списка.

Однако, если исходный массив уже отсортирован, можно значительно ускорить поиск, применив двоичный (бинарный) поиск. Суть подхода заключается в том, чтобы разбить список пополам. На основе значения медианного элемента мы переходим либо в левую, либо в правую половины списка. Таким образом, длина искомого участка уменьшается вдвое на каждом шаге, что приводит к общей сложности алгоритма O(log n).

Алгоритм бинарного поиска

Задача — определить, содержится ли элемент `key` в списке или его части.

• Мы будем сужать область поиска, устанавливая два рубежа (границы) — `left` и `right`.
• Мы знаем, что элемент `A[right]` будет строго больше `key`, что справедливо и для всех элементов к правее `right`.
• Элементы, находящиеся на `left` и слева от него, гарантированно меньше или равны `key`.
• О элементах между `A[left]` и `A[right]` (то есть элементы с индексами больше `left`, но меньше `right`) мы не имеем предположений.

В начале алгоритма установим `left = -1` и `right = len(A)`. Это можно визуализировать как добавление двух фиктивных элементов к краям массива: в левый конец — элемент, равный минус бесконечности (т.е. значение, которое всегда меньше `key`), с индексом `-1`, и в правый конец — элемент, равный плюс бесконечности, с индексом `len(A)`. Таким образом, изначально `left` и `right` указывают на эти фиктивные элементы (фактически в массив ничего добавлять не нужно, это лишь мысленный процесс).

Далее необходимо разделить отрезок от `left` до `right` на два сегмента и получить значение среднего элемента. Его индекс рассчитывается как `middle = (left + right) // 2`. Сравниваем значение этого элемента с `key`. Если `A[middle]` больше `key`, это значит, что `A[middle]` и все элементы правее него следует считать правой частью, что требует присвоить `right = middle`. В противном случае (если `A[middle] <= key`), элемент `A[middle]` и компоненты левее него, относятся к левой части, значит, нужно установить `left = middle`.

Этот процесс повторяется до тех пор, пока между `left` и `right` остаются элементы, т.е. пока `right > left + 1`.

Итак, получаем алгоритм:

```python

left = -1

right = len(A)

while right > left + 1:

     middle = (left + right) // 2

     if A[middle] > key:

          right = middle

     else:

          left = middle

```

После завершения алгоритма `left` и `right` направляют к двум соседним элементам, при этом выполняется условие `A[right] > key`, а `A[left] <= key`. Следовательно, в случае нахождения элемента `key` в списке, то `A[left]` равен `key`. Тем не менее, существует сценарий, когда `left == -1` (если все элементы в массиве `A` строго больше `key`), ввиду этого для подтверждения присутствия элемента `key` в списке необходимо проверить условие:

```python

left >= 0 and A[left] == key

```

Что касается значения `right`, оно указывает на минимальный элемент в списке, который строго больше `key`. Говоря иначе, на позицию элемента `A[right]` можно внедрить элемент со значением `key` (для этого необходимо сдвинуть всю правую часть списка на один элемент) без нарушения порядка. Таким образом, `right` представляет собой «верхнюю границу» для элемента `key`: все, что находится правее этой позиции не может принять элемент `key`, чем сохраняет упорядоченность списка.

Функции для поиска границ в массиве на Python

Функция для поиска «верхней границы»

В приведенной ниже функции `UpperBound` осуществляется поиск верхней границы для заданного элемента `key` в списке `A`:

```python

def UpperBound(A, key):

     left = -1

     right = len(A)

     while right > left + 1:

          middle = (left + right) // 2

     if A[middle] > key:

          right = middle

     else:

          left = middle

          return right

```

Модификация для поиска «нижней границы»

После вышеизложенного модифицируем алгоритм двоичного поиска таким образом, чтобы элементы, равные `key`, располагались в правой части списка, но не в левой, как это было ранее. Этот процесс требует изменения условия в цикле:

```python

def LowerBound(A, key):

     left = -1

     right = len(A)

     while right > left + 1:

          middle = (left + right) // 2

          if A[middle] >= key:

               right = middle

          else:

               left = middle

         return right

```

Завершение цикла

На каком значении завершится цикл для `left` и `right`?

Получаем `A[left] < key` и `A[right] >= key`. Это означает, что элемент со значением `key` можно вставить на место `A[right]` без нарушения порядка, и это будет минимальной позицией для его вставки. К тому же, настоящая функция возвращает «нижнюю границу» для элемента `key`.

Связь между UpperBound и LowerBound

Важно отметить, что функция `UpperBound` возвращает индекс первого элемента, который больше, чем `key`, в то время как `LowerBound` возвращает индекс первого элемента, который равен `key` (или, если такого нет, индекс первого элемента, который больше, чем `key`). Следовательно, разница между `UpperBound(A, key)` и `LowerBound(A, key)` соответствует количеству вхождений элемента `key` в списке `A`.

С помощью функции `LowerBound` также можно проверить наличие элемента `key` в списке `A`, используя условие:

```python

right < len(A) and A[right] == key

```

Это условие позволяет определить, содержится ли элемент в массиве.