Javascript program to count 1's in sorted binary array

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

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

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!