Какова будет сложность двоичного поиска, чтобы найти второе по величине число в массиве

Question

Может кто-нибудь объяснить, как вычислить сложность двоичного поиска, чтобы найти второе по величине число в массиве.

Answer 1

Двоичный поиск выполняется по отсортированному массиву. Если у вас уже есть отсортированный массив, зачем вам вообще что-то делать?

Вторым по последнему числу в массиве (отсортированном в порядке возрастания) будет второе по величине число. (O (1))

Еслимассив содержит дубликаты:

Например, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, ...}

Сложность по времени будет O (log n) , где n - количество элементов в массиве.

Наименьшее число - это однос индексом 0 (назовите его x), теперь вы можете использовать бинарный поиск, чтобы найти границы массива, внутри которых все элементы равны x. Непосредственный сосед за этими границами будет вторым по величине числом в массиве.

Если вы используете C ++, вы можете использовать этот метод для получения upper_bound.

Answer 2

Один из способов сделать это в Python эффективно - преобразовать список [который позволяет дублировать], чтобы установить [который не позволяет дублировать] почти за O (1) время, а затем снова извлечь элемент с индексом [-2] в O(1) время, при условии, что список двоичного поиска будет отсортирован в порядке возрастания.

Answer 3

Бинарный поиск элемента с любым заданным свойством всегда является логарифмическим, при условии, что вы можете определить в постоянном времени, сохраняется ли это свойство.

Если массив не может содержать дубликаты, вам не нужнобинарный поиск и сложность постоянна.