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 id="Find-Smallest-Missing-Number">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 id="Find-Smallest-Missing-Number">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 id="Find-Smallest-Missing-Number">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 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!
Replace String Characters in JavaScriptMar 11, 2025 am 12:07 AMDetailed explanation of JavaScript string replacement method and FAQ This article will explore two ways to replace string characters in JavaScript: internal JavaScript code and internal HTML for web pages. Replace string inside JavaScript code The most direct way is to use the replace() method: str = str.replace("find","replace"); This method replaces only the first match. To replace all matches, use a regular expression and add the global flag g: str = str.replace(/fi
8 Stunning jQuery Page Layout PluginsMar 06, 2025 am 12:48 AMLeverage jQuery for Effortless Web Page Layouts: 8 Essential Plugins jQuery simplifies web page layout significantly. This article highlights eight powerful jQuery plugins that streamline the process, particularly useful for manual website creation
Build Your Own AJAX Web ApplicationsMar 09, 2025 am 12:11 AMSo here you are, ready to learn all about this thing called AJAX. But, what exactly is it? The term AJAX refers to a loose grouping of technologies that are used to create dynamic, interactive web content. The term AJAX, originally coined by Jesse J
10 Mobile Cheat Sheets for Mobile DevelopmentMar 05, 2025 am 12:43 AMThis post compiles helpful cheat sheets, reference guides, quick recipes, and code snippets for Android, Blackberry, and iPhone app development. No developer should be without them! Touch Gesture Reference Guide (PDF) A valuable resource for desig
Improve Your jQuery Knowledge with the Source ViewerMar 05, 2025 am 12:54 AMjQuery is a great JavaScript framework. However, as with any library, sometimes it’s necessary to get under the hood to discover what’s going on. Perhaps it’s because you’re tracing a bug or are just curious about how jQuery achieves a particular UI
10 jQuery Fun and Games PluginsMar 08, 2025 am 12:42 AM10 fun jQuery game plugins to make your website more attractive and enhance user stickiness! While Flash is still the best software for developing casual web games, jQuery can also create surprising effects, and while not comparable to pure action Flash games, in some cases you can also have unexpected fun in your browser. jQuery tic toe game The "Hello world" of game programming now has a jQuery version. Source code jQuery Crazy Word Composition Game This is a fill-in-the-blank game, and it can produce some weird results due to not knowing the context of the word. Source code jQuery mine sweeping game
How do I create and publish my own JavaScript libraries?Mar 18, 2025 pm 03:12 PMArticle discusses creating, publishing, and maintaining JavaScript libraries, focusing on planning, development, testing, documentation, and promotion strategies.
jQuery Parallax Tutorial - Animated Header BackgroundMar 08, 2025 am 12:39 AMThis tutorial demonstrates how to create a captivating parallax background effect using jQuery. We'll build a header banner with layered images that create a stunning visual depth. The updated plugin works with jQuery 1.6.4 and later. Download the
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Zend Studio 13.0.1
Powerful PHP integrated development environment
mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),
Notepad++7.3.1
Easy-to-use and free code editor
ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment
VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft
