search

Home >Web Front-end >JS Tutorial >Javascript program to count 1's in sorted binary array

Javascript program to count 1's in sorted binary array

WBOY
WBOYforward
2023-08-23 21:57:13760browse

Javascript 程序对已排序的二进制数组中的 1 进行计数

We have two ways to count 1's in a sorted binary array. The first is to iterate over the array and count the number of 1's. The second method is to use the binary search algorithm to find the first occurrence of 1 in the array.

It should be noted that in order to use these methods, the array must be sorted.

In this blog post, we will discuss a JavaScript program to count the number of 1’s in a sorted binary array. We will also look at some edge cases and optimization techniques to make the program more efficient.

Problem Statement

Given a sorted binary array, the task is to count the number of 1's in the array. Arrays can be of any size and their elements can only be 0 or 1.

enter

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

Output

 3

method 1

The first method that comes to mind is to iterate over the array and count the number of 1's.

  • Initialize a count variable to store the number in the array.

  • Iterate over the array and check each element. If the current element is equal to 1, increment the counter.

Example

<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>

However, the time complexity of this method is O(n), where n is the size of the array, since we want to iterate through the entire array once.

This can be optimized by taking advantage of the fact that the array is sorted.

Method 2

To find the first instance of 1 in an array, use the binary search method. Simply subtract the index of the first 1 instance from the total number of items in the array to get the number of 1's.

  • In this implementation, we use the "first occurrence" binary search technique to find the first instance of 0 in the array.

  • The low and high variables are initially set to the first and last index of the array, respectively.

  • The number of items in the array is also specified as the value of a variable named firstOne, which will be used to record the index of the first instance of the number 1.

  • The while loop will continue to run until the low index is greater than or equal to the high index. After each iteration, we determine the midpoint of the current range.

  • If the middle element is 1, update the firstOne variable and move the high index to the earlier element. If the element at the midpoint is 0, we move the lower index to the subsequent element.

  • After the while loop completes, we check if the first variable corresponds to the -1 value of the array. If it is, it means there is no 1 in the array, so 1 is returned. If not, return firstOne minus arr.length.

Example

<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>

The time complexity of this method is O(log n), which is much more efficient than the previous method.

In this tutorial, we discussed a JavaScript program to count the number of 1's in a sorted binary array.

The above is the detailed content of Javascript program to count 1's in sorted binary array. For more information, please follow other related articles on the PHP Chinese website!

Statement：
This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete
Previous article：How to get the scaled height of text using FabricJS?Next article：How to get the scaled height of text using FabricJS?

Related articles

See more