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