Javascript program to count 1's in sorted binary array-JS Tutorial-php.cn

Home

Web Front-end

JS Tutorial

Javascript program to count 1's in sorted binary array

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Aug 23, 2023 pm 09:57 PM

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

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. If there is any infringement, please contact admin@php.cn delete

JavaScript in Action: Real-World Examples and ProjectsApr 19, 2025 am 12:13 AM

JavaScript's application in the real world includes front-end and back-end development. 1) Display front-end applications by building a TODO list application, involving DOM operations and event processing. 2) Build RESTfulAPI through Node.js and Express to demonstrate back-end applications.

JavaScript and the Web: Core Functionality and Use CasesApr 18, 2025 am 12:19 AM

The main uses of JavaScript in web development include client interaction, form verification and asynchronous communication. 1) Dynamic content update and user interaction through DOM operations; 2) Client verification is carried out before the user submits data to improve the user experience; 3) Refreshless communication with the server is achieved through AJAX technology.

Understanding the JavaScript Engine: Implementation DetailsApr 17, 2025 am 12:05 AM

Understanding how JavaScript engine works internally is important to developers because it helps write more efficient code and understand performance bottlenecks and optimization strategies. 1) The engine's workflow includes three stages: parsing, compiling and execution; 2) During the execution process, the engine will perform dynamic optimization, such as inline cache and hidden classes; 3) Best practices include avoiding global variables, optimizing loops, using const and lets, and avoiding excessive use of closures.

Python vs. JavaScript: The Learning Curve and Ease of UseApr 16, 2025 am 12:12 AM

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

Python vs. JavaScript: Community, Libraries, and ResourcesApr 15, 2025 am 12:16 AM

Python and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.

From C/C to JavaScript: How It All WorksApr 14, 2025 am 12:05 AM

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

JavaScript Engines: Comparing ImplementationsApr 13, 2025 am 12:05 AM

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

Beyond the Browser: JavaScript in the Real WorldApr 12, 2025 am 12:06 AM

JavaScript's applications in the real world include server-side programming, mobile application development and Internet of Things control: 1. Server-side programming is realized through Node.js, suitable for high concurrent request processing. 2. Mobile application development is carried out through ReactNative and supports cross-platform deployment. 3. Used for IoT device control through Johnny-Five library, suitable for hardware interaction.

See all articles