Programa Javascript para contar 1 en una array binaria ordenada

Dada una array binaria ordenada en orden no creciente, cuente el número de 1 en ella. 

Ejemplos: 

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

Una solución simple es atravesar linealmente la array. La complejidad temporal de la solución simple es O(n). Podemos usar la búsqueda binaria para encontrar el conteo en el tiempo O (Inicio de sesión). La idea es buscar la última aparición de 1 utilizando la búsqueda binaria. Una vez que encontramos la última ocurrencia del índice, devolvemos el índice + 1 como conteo.
La siguiente es la implementación de la idea anterior. 

<script>
  
// Javascript program to count one's in a boolean array
  
/* Returns counts of 1's in arr[low..high].  The array is
   assumed to be sorted in non-increasing order */
function countOnes( arr, low, high)
{
  if (high >= low)
  {
    // get the middle index
    let mid = Math.trunc(low + (high - low)/2);
  
    // check if the element at middle index is last 1
    if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
      return mid+1;
  
    // If element is not last 1, recur for right side
    if (arr[mid] == 1)
      return countOnes(arr, (mid + 1), high);
  
    // else recur for left side
    return countOnes(arr, low, (mid -1));
  }
  return 0;
}
    // Driver program 
      
   let arr = [ 1, 1, 1, 1, 0, 0, 0 ];
   let n = arr.length;
   document.write("Count of 1's in given array is " + 
                    countOnes(arr, 0, n-1));
      
</script>

Count of 1's in given array is 4

La complejidad temporal de la solución anterior es O (Iniciar sesión)

Complejidad espacial o(log n) (pila de llamadas de función)

El mismo enfoque con solución iterativa sería

<script>
/* Returns counts of 1's in arr[low..high].  The array is
   assumed to be sorted in non-increasing order */
  
function countOnes(arr,n)
{
    let ans;
    let low = 0, high = n - 1;
    while (low <= high) { // get the middle index
        let mid = Math.floor((low + high) / 2);
   
        // else recur for left side
        if (arr[mid] < 1)
            high = mid - 1;
        // If element is not last 1, recur for right side
        else if (arr[mid] > 1)
            low = mid + 1;
        else
        // check if the element at middle index is last 1
        {
            if (mid == n - 1 || arr[mid + 1] != 1)
                return mid + 1;
            else
                low = mid + 1;
        }
    }
}
  
let arr=[ 1, 1, 1, 1, 0, 0, 0];
let n = arr.length;
document.write( "Count of 1's in given array is "+ countOnes(arr, n));
  
  
// This code is contributed by unknown2108
</script>

Count of 1's in given array is 4

La complejidad temporal de la solución anterior es O (Iniciar sesión)

La complejidad del espacio es O(1)

Consulte el artículo completo sobre Count 1’s en una array binaria ordenada para obtener más detalles.