Home  >  Article  >  Web Front-end  >  JavaScript program to find the smallest missing number

JavaScript program to find the smallest missing number

PHPz
PHPzforward
2023-09-01 15:29:071188browse

用于查找最小缺失数字的 JavaScript 程序

We are given a sorted array of different non-negative integers, where we have to find the smallest missing number. Therefore, in this tutorial, we will explore different ways to solve this problem and discuss its time complexity with various examples.

Understanding Questions

The problem description is very simple. Given a sorted array of different non-negative integers, we need to find the smallest missing number in it. Let us take an example to understand this problem.

Example

Suppose we have an array [1, 2, 4, 5, 6]. Here we can see that there is a space between the numbers 2 and 4 in this array. This discrepancy indicates that a number is missing. Now we have to find the smallest number that fits the position.

To determine whether a number is missing, we first need to check whether the array contains the number 3. If the number 3 does not exist in the array, we can say that it is a missing number because the number 3 is not contained in the array.

Now let's look at some ways to solve this problem.

Method 1: Naive method

One of the easiest ways to solve this problem is to loop through the array and make sure each item is in the correct position. If the element is not in the correct position, we find the minimum number of missing elements.

Example

This is the code explained above -

<!DOCTYPE html>
<html>
<body>
   <h2>Find Smallest Missing Number</h2>
   <p>Array: [0, 1, 2, 3, 5, 6]</p>
   <p>Result: <span id="result"></span></p>
   <script>
      function findSmallestMissingNumber(arr) {
         let n = arr.length;
         for (let i = 0; i < n; i++) {
            if (arr[i] !== i) {
               return i;
            }
         }
         return n;
      }
      const arr = [0, 1, 2, 3, 5, 6];
      const result = findSmallestMissingNumber(arr);
      document.getElementById("result").innerHTML = result;
   </script>
</body>
</html>

Since we need to traverse the entire array, the time complexity of this method is O(n).

However, this solution is inefficient because it does not take advantage of the fact that we are provided with a sorted array.

Method 2: Binary search method

Here, we will use the binary search method to solve this problem more efficiently. In this method we perform a binary search for the first element that is not present in the array. The code for this method is -

Example

<!DOCTYPE html>
<html>
<body>
   <div id="result"></div>
   <script>
      function findSmallestMissingNumber(arr) {
         let n = arr.length;
         let low = 0;
         let high = n - 1;
         let mid = 0;
         while (high - low > 1) {
            mid = Math.floor((low + high) / 2);
            if (arr[mid] - mid !== arr[low] - low) {
               high = mid;
            } else if (arr[mid] - mid !== arr[high] - high) {
               low = mid;
            }
         }
         return arr[low] + 1;
      }
      const arr = [0, 1, 2, 3, 4, 5, 6, 8];
      const result = findSmallestMissingNumber(arr);
      document.getElementById("result").innerHTML = "Array: " + JSON.stringify(arr) ;
      document.getElementById("result").innerHTML += "<br>The smallest missing number is: " + result;
   </script>
</body>
</html>

Since we are doing a binary search, the time complexity of the above method is O(log n).

This method is more efficient than our simple method because it takes advantage of the fact that the array is sorted.

Method 3: Linear search method

The third method we will discuss is the linear search method. This method relies on the fact that the array is sorted, which will allow us to apply a linear search to identify missing numbers.

The linear search method works by iterating over the array and comparing each member to its index. If the index of an element is not equal to its value, the missing element is somewhere else in the array before that element. We return the index of the missing element.

Example

The code for the linear search method is as follows -

<!DOCTYPE html>
<html>
<body>
   <h2>Find Smallest Missing Number</h2>
   <p>Array: [1, 2, 3, 5]</p>
   <p>Result: <span id="result"></span></p>
   <script>
      function findSmallestMissingNumber(arr) {
         for (let i = 0; i < arr.length; i++) {
            if (arr[i] !== i+1) {
               return i+1;
            }
         }
         return arr.length+1;
      }
      const arr = [1, 2, 3, 5];
      const result = findSmallestMissingNumber(arr);
      document.getElementById("result").innerHTML = result;
   </script>
</body>
</html>

The time complexity of this method is O(n) because we have to iterate the entire array.

This method is less efficient than the binary search method, but is useful for small arrays.

Method 4: Improved binary search

The fourth method we will discuss is the improved binary search method. This method is very similar to the binary search method, except that instead of comparing the middle element to the missing integer, we compare it to its index.

The basic idea behind the modified binary search method is to split the array in half at each step and compare the middle element with its index. If the middle element is greater than its index, the missing member must be in the left half of the array. If the middle element is equal to or less than its index, the missing element must be in the right half of the array.

Example

This is the code implementation of the modified binary search method -

<!DOCTYPE html>
<html>
<body>
   <h2>Find Smallest Missing Number</h2>
   <p>Predefined array:</p>
   <pre id="inputArray">

<script> // Define the input array const inputArray = [0, 1, 2, 3, 4, 6, 7, 8]; // Display the input array in the pre tag document.getElementById("inputArray").innerHTML = JSON.stringify(inputArray); function findMissingNumber() { // Call the findSmallestMissingNumber function to get the result const result = findSmallestMissingNumber(inputArray); // Display the result using the innerHTML method document.getElementById("result").innerHTML = `The smallest missing number is: ${result}`; } // Copy the findSmallestMissingNumber function here function findSmallestMissingNumber(arr) { let left = 0; let right = arr.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] > mid) { right = mid - 1; } else { left = mid + 1; } } return left; } </script>

The time complexity of this method is also O(log n), which is the same as the binary search method.

This method is more efficient than the linear search method and requires the array to be sorted.

in conclusion

In this blog, we discussed four methods to find the smallest missing number from an array. These are naive method, binary search method, linear search method and modified binary search method.

The above is the detailed content of JavaScript program to find the smallest missing number. 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