Программа Php для подсчета 1 в отсортированном двоичном массиве

Дан двоичный массив, отсортированный в порядке невозрастания, подсчитайте количество единиц в нем.

Примеры:

Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2

Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7

Input: arr[] = {0, 0, 0, 0, 0, 0, 0}
Output: 0

Простое решение состоит в том, чтобы линейно пройти массив. Временная сложность простого решения составляет O(n). Мы можем использовать бинарный поиск, чтобы найти число за время O(Logn). Идея состоит в том, чтобы найти последнее вхождение 1 с помощью двоичного поиска. Как только мы находим последнее вхождение индекса, мы возвращаем индекс + 1 в качестве счетчика.
Ниже приведена реализация вышеуказанной идеи.

Временная сложность приведенного выше решения составляет O (Logn).

Пространственная сложность o (log n) (стек вызовов функций)

Пожалуйста, обратитесь к полной статье о счете 1 в отсортированном двоичном массиве для получения более подробной информации!