Javascript程序在已排序的二进制数组中计算1

我们有两种方法来计算一个已排序的二进制数组中的1。第一种是遍历数组并计算1的数量。第二种方法是使用二进制搜索算法来寻找数组中第一次出现的1。

值得注意的是，为了使用这些方法，数组必须被排序。

在这篇博文中，我们将讨论一个JavaScript程序来计算一个排序的二进制数组中的1的数量。我们还将研究一些边缘案例和优化技术，以使程序更有效率。

问题陈述

给定一个排序的二进制数组，任务是计算该数组中1的数量。该数组可以是任何大小，元素只能是0或1。

输入

 bin_array[] = {0, 0, 0,1,1,1}

输出

方法1

我想到的第一个方法是遍历数组并计算1的数量。

初始化一个count变量来存储数组中1的数量。
遍历数组并检查每个元素。如果当前元素等于1，就增加计数器。

例子

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones( bin_array,n) {
         let num_of_ones=0;
         for (let ind = 0; ind < n; ind++) {
            if(bin_array[ind]==1){
               num_of_ones++;
            }
         }
         return num_of_ones;
      }
      let bin_array = [0,0,0,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

然而，这种方法的时间复杂度为O(n)，其中n是数组的大小，因为我们要对整个数组进行一次遍历。

这可以通过利用数组被排序的事实进行优化。

方法2

为了找到数组中第一个1的实例，使用二进制搜索方法。简单地从数组中的项目总数中减去第一个1的索引就可以得到1的数量。

在这个实现中，我们使用 “首次出现 “的二进制搜索技术来寻找数组中第一个0的实例。
低变量和高变量最初被相应地设置为数组的第一个和最后一个索引。
数组中的项目数也被指定为一个名为firstOne的变量的值，它将被用来记录数字1的第一个实例的索引。
直到低索引大于高值或等于它，while循环将一直运行。每次迭代后，我们确定当前范围的中点。
如果位于中点的元素是1，firstOne变量被更新，高指数被移到较早的元素。如果中间点的元素是0，我们就把低索引移到后面的元素。
一旦while循环完成，我们检查firstOne变量是否与数组的-1值相对应。如果是，这意味着数组中没有1，我们返回1。如果不是，则返回firstOne减去arr.length。

例子

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones(bin_arr,low,high) {
         var low = 0;
         var high = bin_arr.length - 1;
         var firstOne = -1;
         while (low <= high) {
            var mid = Math.floor((low + high) / 2);
            if (bin_arr[mid] == 1) {
               firstOne = mid;
               high = mid -1;
            } else {
               low = mid + 1;
            }
         }
         return firstOne == -1 ? 0 : bin_arr.length - firstOne;
      }
      let bin_array = [0,0,0,1,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

这种方法的时间复杂度为O(log n)，比之前的方法要有效得多。

在本教程中，我们讨论了一个JavaScript程序来计算一个排序的二进制数组中的1的数量。